Course - Computational Complexity HT25

This course covers the basics of computational complexity, which studies the amount of resources required to solve certain computational problems, and looks at the relationships between these problems and resources.

Some of the resources considered are: time, space, non-determinism, non-uniformity and randomness. Problems can be collected into “complexity classes” which group together problems with the same resource requirements, such as:

• $\mathsf P$: Problems solvable in polynomial time using a deterministic Turing machine.
• $\mathsf{EXP}$: Problems solvable in time $2^{\text{poly}(n)}$ using a deterministic Turing machine.
• $\mathsf{PSPACE}$: Problems solvable in deterministic polynomial space.
• $\mathsf{NP}$: Problems solvable by a non-deterministic Turing machine in polynomial time.
• $\mathsf{P} _ {/\text{poly}}$: Problems solvable in polynomial time using a deterministic Turing machine with polynomial-sized advice, or equivalently solvable using a family of polynomially-sized circuits.
• $\mathsf{BPP}$: Problems solvable with appropriately bounded probability of error using a randomised Turing machine.
  
  There’s a lot that’s not known about the relationship between these classes. The most famous open problem is $\mathsf{P} \stackrel?= \mathsf{NP}$, which effectively asks whether any problem for which the solution can be efficiently verified can also be efficiently solved. There is a few things we do know; one of the surprising results is that $\mathsf{PSPACE} = \mathsf{NPSPACE}$, this follows from a result called Savitch’s theorem.

• Course webpage
• Lecture notes:
  • 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 (old)
  • 14, Error reduction and randomness vs non-uniformity: notes (old)
  • 15, Approximation and the PCP theorem: notes (old)
  • 16, Approximation and the PCP theorem: notes (old)
• My notes here are based on the lecture notes above, written by Prof. Rahul Santhanam and the textbooks “Computational Complexity: A Modern Approach” by Arora and Barak, and “Introduction to the Theory of Computation” by Sipser.
• Other courses this term: Courses HT25^U
• Other related courses and notes:
  • Course - Models of Computation MT23^U
  • Course - Algorithms and Data Structures HT24^U
  • Quantum Computing Since Democritus, Aaronson^N
• Related blog posts:
  • Finding the shortest route between every Oxford college^B

Notes

• Notes - Computational Complexity HT25, Basic definitions^U
• Notes - Computational Complexity HT25, Mapping reductions^U
• Notes - Computational Complexity HT25, Time and space^U
• Notes - Computational Complexity HT25, Diagonalisation^U
• Notes - Computational Complexity HT25, Hierarchy theorems^U
• Notes - Computational Complexity HT25, Crossing sequences^U
• Notes - Computational Complexity HT25, Padding arguments^U
• Notes - Computational Complexity HT25, Non-deterministic Turing machines^U
• Notes - Computational Complexity HT25, Savitch’s theorem^U
• Notes - Computational Complexity HT25, Turing reductions^U
• Notes - Computational Complexity HT25, Index of reductions^U
• Notes - Computational Complexity HT25, Cook-Levin theorem^U
• Notes - Computational Complexity HT25, Alternations and polynomial hierarchy^U
• Notes - Computational Complexity HT25, PSPACE completeness^U
• Notes - Computational Complexity HT25, Sublinear space classes^U
• Notes - Computational Complexity HT25, Circuits^U
• Notes - Computational Complexity HT25, Randomness^U
• Notes - Computational Complexity HT25, Approximation^U
• Notes - Computational Complexity HT25, Common proof themes^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, Decideability^U
• Notes - ADS HT24, NP-hardness and NP-completeness^U
• Notes - ADS HT24, Approximation algorithms^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

• Notes - Computational Complexity HT25, Problem sheets^U
• Sheet 1, Problem Sheet - Computational Complexity HT25, I
• Sheet 2, Problem Sheet - Computational Complexity HT25, II
• Sheet 3, redacted^?
• Sheet 4, redacted^?
• Sheet 5, redacted^?
• Sheet 6, redacted^?

To-Do List