Computational Complexity: course materials 2021/2022

Slides, lectures

• slides 1, introduction, motivation
• slides 2, TMs, diagonalisation, reductions
• slides 3, deterministic complexity classes
• slides 4, nondeterminism, Cook-Levin
• slides 5, reductions, NP-hardness
• slides 6, strong NP-hardness, NP vs co-NP, FNP
• slides 7, Space complexity, time/space hierarchy theorems
• slides 8, PSPACE, NPSPACE, QBFs
• slides 9, “geography” game, Alternating TMs
• slides 10, poly hierarchy, logspace (det/non-det)
• slides 11, circuit complexity, NC, P-completeness, AC
• slides 12, RP, BPP, amplification
• slides 13, more randomised complexity, interactive proofs
• slides 14, Space hierarchy theorem, gap theorem, Ladner’s theorem
• slides 15, 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