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 results that surprised me was 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.
• 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
  • [[Computational Complexity, Arora]]^?
• Related blog posts:
  • [[Finding the shortest route between every Oxford college]]^B

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
• [[Notes - Computational Complexity HT25, Boolean circuit model]]^U
• [[Notes - Computational Complexity HT25, Randomness]]^U

• [[Notes - Computational Complexity HT25, Approximation and the PCP theorem]]^U

• ([[Notes - Computational Complexity HT25, Diagram of inclusions.canvas

  Notes - Computational Complexity HT25, Diagram of inclusions]])

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, [[Problem Sheet - Computational Complexity HT25, I]]^?
  • Sheet 2, [[Problem Sheet - Computational Complexity HT25, II]]^?
  • Sheet 3, [[Problem Sheet - Computational Complexity HT25, III]]^?
  • Sheet 4, [[Problem Sheet - Computational Complexity HT25, IV]]^?
  • Sheet 5, [[Problem Sheet - Computational Complexity HT25, V]]^?
  • Sheet 6, [[Problem Sheet - Computational Complexity HT25, VI]]^?

To-Do List