Computational Complexity: course materials

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.

2018/19 course materials

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

slides 15

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.

slides 14

lecture-14a and lecture-14b (recorded)

Space hierarchy theorem, Gap theorem, Ladner's theorem

slides 13

lecture-13a and lecture-13b (recorded)

More on randomised complexity; interactive proofs

slides 12

lecture-12a and lecture-12b (recorded)

Randomised complexity: RP, BPP, probability amplification

slides 11

lecture-11a and lecture-11b (recorded)

introduction to circuit complexity: NC, P-completeness, AC

slides 10

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

slides 9

lecture-9a and lecture-9b (recorded)

PSPACE-completness example (the “geography” game), Alternating Turing machines

slides 8

lecture-8a and lecture-8b (recorded)

PSPACE-completness, PSPACE=NPSPACE, quantified boolean formulae

slides 7

lecture-7a and lecture-7b (recorded)

Getting started on space complexity, time/space hierarchy theorems

slides 6

lecture-6a and lecture-6b (recorded)

strong NP-hardness, NP vs. co-NP, FNP

slides 5

lecture-5a and lecture-5b (recorded)

reductions, NP-hardness

slides 4

lecture-4a and lecture-4b (recorded)

nondeterminism, Cook-Levin theorem

slides 3

lecture-3a and lecture-3b (recorded)

deterministic complexity classes

These slides are used in the two recordings: lecture-3a and lecture-3b

slides 2

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.

slides 1

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.


List of PSPACE-complete problems The diversity of these problems makes the point that PSPACE is an important complexity class

the complexity class P

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)