You are here: Home files Missing notes
Document Actions

Missing notes

Well, this is embarrassing. It seems that I failed to save the notes of this lecture. If anyone in the audience took legible notes, I'd be grateful if you could provide these. I'd scan the notes and publish them here.

 Anyway, content of the lecture were

  • A proof of the Cook-Levin theorem. While crucially important, it is standard material in any text book, so there is a substitute for the lost notes. One proof can be found in the online version of Arora & Barak's book linked from the main page for this lecture. Note that they use the concept of an "oblivious Turing machine" which my proof didn't require (at the expense of using a slightly non-trivial encoding of the tape contents, as initially introduced for the proof of Godel's Incompleteness Theorem).
  • A graph of the "Web of Reductions" , which was copied from Arora & Barak's book draft.
  • A vote on the further progress of the lecture. Non-essential.

 

Personal tools