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.

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**

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. |

Space hierarchy theorem, gap theorem, Ladner’s theorem |
10th Mar: aim to cover these topics |

Randomised complexity classes |
5th Mar: almost completed slides 8 3rd Mar: got as far as topic of amplification |

Circuits, P-completeness |
27th Feb: covered rest of material on Slides 7 25th Feb: start this topic, got as far as P-completeness |

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

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. |

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.**

- Exercises 6 for classes in week 8
- Exercises 5 for classes in week 7
- Exercises 4 for classes in week 6
- Exercises 3 for classes in week 5
- Exercises 2 for classes in week 4
- Exercises 1 for classes in week 3

**Links.**

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)