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 Practise 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 Practise Questions File PDF document
  • 
    Lecture 15: Counting, PSPACE, and beyond File PDF document