Computational Complexity: course materials 2018/2019

Slides, lectures

• slides 1, introduction, motivation
• slides 2, Turing machines, undecidability
• slides 3, Halting problem, reductions
• slides 4, Deterministic complexity classes, PTIME etc
• slides 5, nondeterminism, Cook-Levin theorem, NP-completeness
• slides 6, Space complexity
• slides 7, Logarithmic space
• slides 8, circuit complexity
• slides 9, randomisation
• slides 10, classes of total search problems

Exercise sheets.

• Exercises 1 for classes in week 3
• Exercises 2 for classes in week 4
• Exercises 3 for classes in week 5
• Exercises 4 for classes in week 6
• Exercises 5 for classes in week 7
• Exercises 6 for classes in week 8