Course - Computational Complexity HT25

• Course Webpage
• Lecture Notes
• From the previous year:
  • 1, Motivation and recap of Turing machines: notes
  • 2, Reducibility and diagonalisation: notes
  • 3, Time and space: notes
  • 4, Hierarchy theorems: notes
  • 5, Non-deterministic Turing machines: notes
  • 6, Deterministic vs non-deterministic classes: notes
  • 7, Non-determinism and NP-completeness: notes
  • 8, The Cook-Levin theorem: notes
  • 9, Turing reductions and alternations: notes
  • 10, PSPACE-completeness: notes
  • 11, Circuit complexity and non-uniformity: notes
  • 12, Time vs non-uniformity and P-completeness: notes
  • 13, Randomness as a resource: notes
  • 14, Error reduction and randomness vs non-uniformity: notes
  • 15, Approximation and the PCP theorem: notes
  • 16, Approximation and the PCP theorem: notes
• Other courses this term: [[Courses HT25]]^U
• Other related courses:
  • [[Course - Models of Computation MT23]]^U
  • [[Course - Algorithms and Data Structures HT24]]^U

Notes

• [[Notes - Computational Complexity HT25, Properties of languages]]^U
• [[Notes - Computational Complexity HT25, Mapping reductions]]^U
• [[Notes - Computational Complexity HT25, Time and space]]^U
• [[Notes - Computational Complexity HT25, Nondeterminism]]^U
• [[Notes - Computational Complexity HT25, Savitch’s theorem]]^U
• [[Notes - Computational Complexity HT25, Turing reductions]]^U
• [[Notes - Computational Complexity HT25, Cook-Levin theorem]]^U
• [[Notes - Computational Complexity HT25, Polynomial hierarchy]]^U
• [[Notes - Computational Complexity HT25, PSPACE-completeness]]^U
• [[Notes - Computational Complexity HT25, Sublinear space classes]]^U

Related notes

The start of the course has significant overlap with:

• [[Notes - Models of Computation MT23, Turing machines]]^U
• [[Notes - Models of Computation MT23, Basic definitions]]^U
• [[Notes - Models of Computation MT23, Languages]]^U
• [[Notes - Models of Computation MT23, Decidability]]^U
• [[Notes - ADS HT24, NP-hardness and NP-completeness]]^U

The presentation of this material is slightly different, e.g. in this course the main model of computation discussed in a $k$-tape Turing machine, but in [[Course - Models of Computation MT23]]^U, Turing machines were primarily discussed in a single-tape context).

Problem Sheets

• From the previous year:
  • Sheet 1
  • Sheet 2
  • Sheet 3, [[Problem Sheet - Computational Complexity HT25, III]]^?
  • Sheet 4, [[Problem Sheet - Computational Complexity HT25, IV]]^?
  • Sheet 5
  • Sheet 6

To-Do List