This page is maintained by Paul Goldberg, teaching Computational Complexity in Hilary term 2020–21; 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:**
on-line, pre-recorded, Q&A sessions on Teams at 9am on Thursdays.

**Classes:**
Problem-based exercise classes in weeks **3,5,7,8**.
(timetable,
6 class groups, tutors are Matthew Katzman, Caterina Viola, Levente
Bodnár, Mohammad Karamlou)

**Hand in exercises** by (time TBA) 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.

**Slides, lectures**

lecture-15a, lecture-15b, and lecture-15c (recorded) Final set of slides |
NP search/function problems (FNP), and total search problems (TFNP) A more specialised topic, relating to my research: various diverse problems involve searching for solutions that are guaranteed to exist, but seem to be computationally hard. This can happen when the existence proof does not provide a polynomial-time algorithm, but uses a ‘computationally inefficient’ existence principle. We examine why we need to use further complexity classes to classify these problems, and the evidence that the problems are indeed hard. |

lecture-14a and lecture-14b (recorded) |
Space hierarchy theorem, Gap theorem, Ladner's theorem |

lecture-13a and lecture-13b (recorded) |
More on randomised complexity; interactive proofs |

lecture-12a and lecture-12b (recorded) |
Randomised complexity: RP, BPP, probability amplification |

lecture-11a and lecture-11b (recorded) |
introduction to circuit complexity: NC, P-completeness, AC |

lecture-10a, lecture-10b, and lecture-10c (recorded) |
First part: the Polynomial hierarchy (complexity classes intermediate between NP and PSPACE). Then in the second two recordings, I switch to subclasses of P, in particular computation in logarithmic space, deterministic and non-deterministic |

lecture-9a and lecture-9b (recorded) |
PSPACE-completness example (the “geography” game), Alternating Turing machines |

lecture-8a and lecture-8b (recorded) |
PSPACE-completness, PSPACE=NPSPACE, quantified boolean formulae |

lecture-7a and lecture-7b (recorded) |
Getting started on space complexity, time/space hierarchy theorems |

lecture-6a and lecture-6b (recorded) |
strong NP-hardness, NP vs. co-NP, FNP |

lecture-5a and lecture-5b (recorded) |
reductions, NP-hardness |

lecture-4a and lecture-4b (recorded) |
nondeterminism, Cook-Levin theorem |

lecture-3a and lecture-3b (recorded) |
deterministic complexity classes These slides are used in the two recordings: lecture-3a and lecture-3b |

lecture-2a and lecture-2b (recorded) |
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. |

lecture-1a and lecture-1b (recorded) |
lecture 1: 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. |

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

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

**Links.**

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)