This page is maintained by Paul Goldberg, teaching Computational Complexity in Hilary term 2022–23; please re-visit this page since it is updated regularly.
my “official” web page; my detailed web page; CS Dept all courses; Computational Complexity course
Lectures: 10am on Tuesday and Thursday, weeks 1–8, LT.A. (timetable)
I will usually be free to talk after lectures.
Classes: Problem-based exercise classes in weeks 3–8. timetable, tutors: Andrew Ryzhikov (classes Friday 2pm 051), Paulina Smolarova (classes Friday 3pm TH RHB)
Hand in exercises by 5pm on previous Wednesday email to the marker.
Textbooks: Computational Complexity: A Modern Approach by Arora and Barak. Introduction to the Theory of Computation 2nd Edition by Mike Sipser. Computational Complexity by Papadimitriou.
Pre-requisite knowledge: You should know basic concepts in Sipser chapter 0 (graphs, boolean logic and operations, mathematical proofs). Also understand the big-O notation used in runtime analysis of algorithms. Turing machines (I will give a reminder, mainly to point out notation), and (un)decidability.
Slides, lectures
|
2 lectures (week 8) |
Further topics: Space hierarchy theorem, Gap theorem, Ladner's theorem Search problems, and total search problems. We see that when a search problem has guaranteed solutions, but the guarantee does not come with a Ptime algorithm, further classes are needed… |
|
2 lectures (week 7) |
Randomised computing, corresponding complexity classes, interactive proofs, zero-knowledge |
|
about 2 lectures |
Polynomial hierarchy, (N)LOGSPACE, Circuit complexity, NC, AC, P-completeness finished covering these slides on 23rd Feb (Thursday week 6) |
|
about 3 lectures |
Space complexity, time/space hierarchy theorems, PSPACE, alternating TMs started these on 7th Feb (Tues week 4); completed PSPACE-completeness of QBF on 9th Feb. |
|
about 3 lectures |
Non-deterministic TMs, NP, Cook-Levin theorem, NP-completeness via reductions, co-NP; NP search and optimisation problems started on these slides on 26th Jan, almost completed them on 2nd Feb. |
|
first 3 lectures |
Lecture 2 (19 Jan) reviews TMs and (un)decidability. Lecture 3 will be on deterministic complexity classes As noted, you should be familiar with big-O notation, notion of a “problem” in algorithmic sense. The slides emphasise the significance of polynomial-time computability. They review Turing machines and propositional logic, but I am hoping you have seen these before, so read up on those if needed. |
Exercise sheets.
Reminder: attempt all exercises on your own – do not search online for answers. That is important for making sure you understand the material.
Some links.
complete problems in the polynomial hierarchy
List of PSPACE-complete problems The diversity of these problems makes the point that PSPACE is an important complexity class
Clay Math Institute Millenium Problems (a different usage of the word “problem” from one I usually have in mind); P vs NP problem (with link to Minesweeper discussion)
Ladner’s theorem from Arora/Barak textbook