Computational Complexity: course materials

This page is maintained by Paul Goldberg, teaching Computational Complexity in Hilary term 2019–20; please re-visit this page since it is updated regularly.

2018/19 course materials

my “official” web page; my detailed web page; CS Dept all courses; Computational Complexity course

Lectures: Tuesdays 12:00–1:00 and Thursdays 4:00–5:00pm, Lecture theatre B, weeks 1 to 8 (official timetable)

I will usually be free to talk after lectures.

Classes: Problem-based exercise classes in weeks 3–8. (see official timetable)

Hand in exercises by (time TBA) in the marker’s pigeon hole.

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.

Slides, lectures

slides 10

Searcch vs. decision problems; total search problems

12th Mar: you do not need to know about the classes of total search problems, but shoud have a general understanding of the relationship between NP decision problems and FNP search problems. Also the reason why total search problems are unlikely to be NP-complete.

slides 9

Space hierarchy theorem, gap theorem, Ladner’s theorem

10th Mar: aim to cover these topics

slides 8

Randomised complexity classes

5th Mar: almost completed slides 8

3rd Mar: got as far as topic of amplification

slides 7

Circuits, P-completeness

27th Feb: covered rest of material on Slides 7

25th Feb: start this topic, got as far as P-completeness

slides 6

Logarithmic space

20th Feb: poly-time hierarchy (end of slides 5). L vs. NL; NL-completeness of Reachability

slides 5

Space complexity

18th Feb: PSPACE-completeness of generalised Geography, and intro to Alternating TMs

13th Feb: PSPACE-completeness of QBF

11th Feb: got as far as Savitch’s theorem on slides.

slides 4

nondeterminism, Cook-Levin, reductions

6th Feb: NP-completeness of various problems; brief mention of Ladner’s theorem, NP versus co-NP

4th Feb: Cook-Levin theorem, and a couple of simple NP-completeness reductions.

30th Jan: NP, certificates, reductions

slides 3

28th Jan: deterministic complexity classes: I got as far as Slide 20

slides 2

23rd Jan: Turing machines, diagonalisation, reductions.

Decision problems correspond to languages. yes-instance of a problem is a word in the language. Distinction between Turing reduction and many-one reduction: the latter are more informative. Later: additional restrictions on reductions make them even more informative. I did not cover the example reductions towards the end of the slides.

slides 1

21st Jan: introduction, motivation.

As noted, you should appreciate the significance of polynomial-time computability, and be familiar with big-O notation, notion of a “problem” in algorithmic sense. I did not have time to work through the 2 slides on CLIQUE but they are not crucial.

Exercise sheets.


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)