Contact
Teaching
 |
 |
|
| Complexity Theory 2016 | ||
 |
 |
| News | Dates | Grading | Content | Exercises | Exam | Material |
Slides and Transparencies
- Lecture 1: slides [PDF]
- Lecture 2: slides [PDF], whiteboard photos for 3color-indset reduction and palindromes and halting problem, see also p.207 of Sipser's book (in the edition linked below)
- Lecture 3: slides [PDF]
- Lecture 4: slides [PDF]
- Lecture 5: slides [PDF]
- Lecture 6: slides [PDF]
- Lecture 7: slides [PDF], whiteboard photo for space hierarchy, see also p.207 of Sipser
- Lecture 8: slides [PDF]
- Lecture 9: slides [PDF], for proof of NL=coNL see also p.355-356 of Sipser, proof of the general Immerman-Szelepcsenyi theorem
- Lecture 10: slides [PDF]
- Lecture 10-Part II: slides [PDF]
- Lecture 11: slides [PDF]
- Lecture 12-13: slides [PDF]
- Lecture 14: slides [PDF]
- Lecture 15: slides [PDF]
- Lecture 16: slides [PDF]
- Lecture 17: slides [PDF]
- Lecture 18: slides [PDF]
- Lecture 19: slides [PDF]
- Lecture 20: slides [PDF]
- Lecture 21: slides [PDF]
- Lecture 22: slides [PDF]
- Lecture 23: slides [PDF]
- Lecture 24: slides [PDF]
- Lecture 25: slides [PDF]
Links
- Turing's original paper: On computable numbers with an application to the Entscheidungsproblem
- Turing machine fun (videos)
- Cook's paper: The complexity of theorem proving procedures
- P vs NP, the epic battle, video
- The 3rd edition of Sipser's book seems to be available online