# Course - Computational Complexity HT25 > Source: https://ollybritton.com/notes/uni/part-b/ht25/computational-complexity/ · Updated: 2025-12-03 · Tags: uni, course > 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](https://courses.cs.ox.ac.uk/course/view.php?name=complexity_2024_2025) - Lecture notes: - 1, Motivation and recap of Turing machines: [notes](https://courses.cs.ox.ac.uk/pluginfile.php/20163/mod_resource/content/1/Lec1.pdf) - 2, Reducibility and diagonalisation: [notes](https://courses.cs.ox.ac.uk/pluginfile.php/20328/mod_resource/content/1/Lec2.pdf) - 3, Time and space: [notes](https://courses.cs.ox.ac.uk/pluginfile.php/20465/mod_resource/content/1/Lec3.pdf) - 4, Hierarchy theorems: [notes](https://courses.cs.ox.ac.uk/pluginfile.php/20748/mod_resource/content/1/Lec4.pdf) - 5, Non-deterministic Turing machines: [notes](https://courses.cs.ox.ac.uk/pluginfile.php/20749/mod_resource/content/1/Lec5.pdf) - 6, Deterministic vs non-deterministic classes: [notes](https://courses.cs.ox.ac.uk/pluginfile.php/20750/mod_resource/content/1/Lec6.pdf) - 7, Non-determinism and NP-completeness: [notes](https://courses.cs.ox.ac.uk/pluginfile.php/21477/mod_resource/content/1/Lec7.pdf) - 8, The Cook-Levin theorem: [notes](https://courses.cs.ox.ac.uk/pluginfile.php/21956/mod_resource/content/1/Lec8.pdf) - 9, Turing reductions and alternations: [notes](https://courses.cs.ox.ac.uk/pluginfile.php/22452/mod_resource/content/1/Lec9.pdf) - 10, PSPACE-completeness: [notes](https://courses.cs.ox.ac.uk/pluginfile.php/22453/mod_resource/content/1/Lec10.pdf) - 11, Circuit complexity and non-uniformity: [notes](https://courses.cs.ox.ac.uk/pluginfile.php/22959/mod_resource/content/1/Lec11.pdf) - 12, Time vs non-uniformity and P-completeness: [notes](https://courses.cs.ox.ac.uk/pluginfile.php/22960/mod_resource/content/1/Lec12.pdf) - 13, Randomness as a resource: [notes](https://courses.cs.ox.ac.uk/pluginfile.php/13260/mod_resource/content/1/Lec13.pdf) (old) - 14, Error reduction and randomness vs non-uniformity: [notes](https://courses.cs.ox.ac.uk/pluginfile.php/13267/mod_resource/content/1/Lec14.pdf) (old) - 15, Approximation and the PCP theorem: [notes](https://courses.cs.ox.ac.uk/pluginfile.php/13268/mod_resource/content/1/Lecs15and16.pdf) (old) - 16, Approximation and the PCP theorem: [notes](https://courses.cs.ox.ac.uk/pluginfile.php/13268/mod_resource/content/1/Lecs15and16.pdf) (old) - My notes here are based on the lecture notes above, written by [Prof. Rahul Santhanam](https://courses.cs.ox.ac.uk/user/profile.php?id=225&course=689) 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](https://ollybritton.com/notes/uni/part-b/ht25/) - Other related courses and notes: - [Course - Models of Computation MT23](https://ollybritton.com/notes/uni/part-a/mt23/models-of-computation/) - [Course - Algorithms and Data Structures HT24](https://ollybritton.com/notes/uni/part-a/ht24/ads/) - [Quantum Computing Since Democritus, Aaronson](https://ollybritton.com/notes/books/quantum-computing-since-democritus/) - Related blog posts: - [Finding the shortest route between every Oxford college](https://ollybritton.com/blog/travelling-scholar-problem/) ### Notes - [Notes - Computational Complexity HT25, Basic definitions](https://ollybritton.com/notes/uni/part-b/ht25/computational-complexity/notes/basic-definitions/) - [Notes - Computational Complexity HT25, Mapping reductions](https://ollybritton.com/notes/uni/part-b/ht25/computational-complexity/notes/mapping-reductions/) - [Notes - Computational Complexity HT25, Time and space](https://ollybritton.com/notes/uni/part-b/ht25/computational-complexity/notes/time-and-space/) - [Notes - Computational Complexity HT25, Diagonalisation](https://ollybritton.com/notes/uni/part-b/ht25/computational-complexity/notes/diagonalisation/) - [Notes - Computational Complexity HT25, Hierarchy theorems](https://ollybritton.com/notes/uni/part-b/ht25/computational-complexity/notes/hierarchy-theorems/) - [Notes - Computational Complexity HT25, Crossing sequences](https://ollybritton.com/notes/uni/part-b/ht25/computational-complexity/notes/crossing-sequences/) - [Notes - Computational Complexity HT25, Padding arguments](https://ollybritton.com/notes/uni/part-b/ht25/computational-complexity/notes/padding-arguments/) - [Notes - Computational Complexity HT25, Non-deterministic Turing machines](https://ollybritton.com/notes/uni/part-b/ht25/computational-complexity/notes/non-deterministic-turing-machines/) - [Notes - Computational Complexity HT25, Savitch's theorem](https://ollybritton.com/notes/uni/part-b/ht25/computational-complexity/notes/savitchs-theorem/) - [Notes - Computational Complexity HT25, Turing reductions](https://ollybritton.com/notes/uni/part-b/ht25/computational-complexity/notes/turing-reductions/) - [Notes - Computational Complexity HT25, Index of reductions](https://ollybritton.com/notes/uni/part-b/ht25/computational-complexity/notes/index-of-reductions/) - [Notes - Computational Complexity HT25, Cook-Levin theorem](https://ollybritton.com/notes/uni/part-b/ht25/computational-complexity/notes/cook-levin-theorem/) - [Notes - Computational Complexity HT25, Alternations and polynomial hierarchy](https://ollybritton.com/notes/uni/part-b/ht25/computational-complexity/notes/alternations-and-polynomial-hierarchy/) - [Notes - Computational Complexity HT25, PSPACE completeness](https://ollybritton.com/notes/uni/part-b/ht25/computational-complexity/notes/pspace-completeness/) - [Notes - Computational Complexity HT25, Sublinear space classes](https://ollybritton.com/notes/uni/part-b/ht25/computational-complexity/notes/sublinear-space-classes/) - [Notes - Computational Complexity HT25, Circuits](https://ollybritton.com/notes/uni/part-b/ht25/computational-complexity/notes/circuits/) - [Notes - Computational Complexity HT25, Randomness](https://ollybritton.com/notes/uni/part-b/ht25/computational-complexity/notes/randomness/) - [Notes - Computational Complexity HT25, Approximation](https://ollybritton.com/notes/uni/part-b/ht25/computational-complexity/notes/approximation/) - [Notes - Computational Complexity HT25, Common proof themes](https://ollybritton.com/notes/uni/part-b/ht25/computational-complexity/notes/common-proof-themes/) ### Related notes The start of the course has significant overlap with: - [Notes - Models of Computation MT23, Turing machines](https://ollybritton.com/notes/uni/part-a/mt23/models-of-computation/notes/turing-machines/) - [Notes - Models of Computation MT23, Basic definitions](https://ollybritton.com/notes/uni/part-a/mt23/models-of-computation/notes/basic-definitions/) - [Notes - Models of Computation MT23, Languages](https://ollybritton.com/notes/uni/part-a/mt23/models-of-computation/notes/languages/) - [Notes - Models of Computation MT23, Decideability](https://ollybritton.com/notes/uni/part-a/mt23/models-of-computation/notes/decideability/) - [Notes - ADS HT24, NP-hardness and NP-completeness](https://ollybritton.com/notes/uni/part-a/ht24/ads/notes/np-hardness-and-np-completeness/) - [Notes - ADS HT24, Approximation algorithms](https://ollybritton.com/notes/uni/part-a/ht24/ads/notes/approximation-algorithms/) 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](https://ollybritton.com/notes/uni/part-a/mt23/models-of-computation/), Turing machines were primarily discussed in a single-tape context). ### Problem Sheets - [Notes - Computational Complexity HT25, Problem sheets](https://ollybritton.com/notes/uni/part-b/ht25/computational-complexity/notes/problem-sheets/) - [Sheet 1](https://courses.cs.ox.ac.uk/pluginfile.php/20162/mod_resource/content/1/sheet1.pdf), Problem Sheet - Computational Complexity HT25, I - [Sheet 2](https://courses.cs.ox.ac.uk/pluginfile.php/20464/mod_resource/content/1/sheet2.pdf), Problem Sheet - Computational Complexity HT25, II - [Sheet 3](https://courses.cs.ox.ac.uk/pluginfile.php/21538/mod_resource/content/1/sheet3.pdf), [redacted](https://ollybritton.com/404) - [Sheet 4](https://courses.cs.ox.ac.uk/pluginfile.php/21957/mod_resource/content/1/sheet4.pdf), [redacted](https://ollybritton.com/404) - [Sheet 5](https://courses.cs.ox.ac.uk/pluginfile.php/22215/mod_resource/content/1/sheet5.pdf), [redacted](https://ollybritton.com/404) - [Sheet 6](https://courses.cs.ox.ac.uk/pluginfile.php/22776/mod_resource/content/1/sheet6.pdf), [redacted](https://ollybritton.com/404) ### To-Do List --- Olly Britton — https://ollybritton.com. Machine-readable index: https://ollybritton.com/llms.txt