**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.**