CS-E4530 - Computational Complexity Theory, 02.01.2017-29.03.2017

Materials

• Materials
  

  Materials

  • Lecture 1: Introduction File PDF document
  • Lecture 2: Turing Machines File PDF document
  • Lecture 3: Nondeterminism, RAM model File PDF document
  • Lecture 4: Universal Turing Machines and Undecidability File PDF document
  • Midterm Practice Questions File PDF document
  • Lecture 5: Boolean logic File PDF document
  • Lecture 6: Complexity classes File PDF document
  • Lecture 7: Reductions and Completeness File PDF document
  • Lecture 8: NP-complete problems File PDF document
  • Lecture 9: co-NP, the structure of NP and relativization File PDF document
  • Lecture 10: Polynomial Hierarchy and Alternations File PDF document
  • Lecture 11 Circuit complexity and parallel computing File PDF document
  • Lecture 12: Randomised computation File PDF document
  • Lecture 13: Cryptography File PDF document
  • Lecture 14: Approximability File PDF document
  • Exam Practice Questions File PDF document
  • Lecture 15: Counting, PSPACE, and beyond File PDF document