Computational Complexity: course materials

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.

2021/22 course materials

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

slides 6

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…

slides 5

2 lectures (week 7)

Randomised computing, corresponding complexity classes, interactive proofs, zero-knowledge

slides 4

about 2 lectures

Polynomial hierarchy, (N)LOGSPACE, Circuit complexity, NC, AC, P-completeness

finished covering these slides on 23rd Feb (Thursday week 6)

slides 3

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.

slides 2

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.

slides 1

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.

the complexity class P

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)

Barak draft textbook

van Melkebeek notes

Ladner’s theorem from Arora/Barak textbook

Panopto recordings