Computational Complexity
University of Amsterdam, April–May 2023

Lecturer: Ronald de Haan
Teaching assistants: Martijn Brehm & Jana Sotáková

Course catalogue


Computational Complexity: A Modern Approach, by Sanjeev Arora and Boaz Barak.

Online discussion board

We will use a dedicated Discourse forum for all (online) discussions on the topics covered in the course. An 'invitation phrase' for this forum (that you need to create an account) is available on Canvas.

(Cartoon by Stefan Szeider—based on the original cartoon from the book Computers and Intractability: A Guide to the Theory of NP-Completeness (1979) by Michael Garey and David S. Johnson.)

Homework and exam

Homework exercises will generally be made available on Wednesdays and have to be handed in on Wednesday one week later. Please hand in your solutions to the homework assignments via Canvas.

Besides the exercises there will be a take-home final exam. The exam will be open book, which means you are allowed to use the book and any notes you made. The final grade for the course will be the average of the grade for the exercises and the final exam.


Tue 4 Apr.  15–17 SP G3.10 Lecture 1: Introduction to computational complexity
Book: 1.0–1.3, 1.6
For visualizations of Turing machines, you can visit
(the Turing machines shown there are bidirectional, see Claim 1.8 in the book).
Wed 5 Apr.  13–15 SP D1.111 Lecture 2: P, NP, coNP, reductions
Book: 1.4, 1.7, 2.0–2.2, 2.6
Thu 6 Apr.  15–17 SP G4.15 Exercise session 1
Exercise sheet
Book: 0.3, 1.1–1.3, 1.6
Wed 12 Apr.  13–15 SP D1.111 Lecture 3: NP-completeness, Cook-Levin Theorem, search vs. decision problems
Book: 2.3–2.5, 2.7
Homework 1
Due: Wed 19 Apr., 23:59
Use this template (pdf) for typesetting Slitherlink gadgets.
Thu 13 Apr.  15–17 SP G4.15 Exercise session 2
Exercise sheet
Fri 14 Apr.  15–17 SP G3.02 Lecture 4: Diagonalization, time hierarchy theorems, Ladner's Theorem
Book: 3.0–3.3
Wed 19 Apr.  13–15 SP D1.111 Lecture 5: Relativization, Baker-Gill-Solovay Theorem
Book: 3.4
Homework 2
Due: Wed 26 Apr., 23:59
Thu 20 Apr.  15–17 SP G4.15 Exercise session 3
Exercise sheet
Fri 21 Apr.  15–17 SP G3.02 Lecture 6: Space complexity, PSPACE, L, NL
Book: Chapter 4
Tue 25 Apr.  11–13 SP G3.02 Lecture 7: Polynomial Hierarchy
Book: Chapter 5
('Parody news article' about the collapse of the PH)
Homework 3
Due: Wed 10 May, 23:59
Wed 26 Apr.  9–11 SP G4.15 Lecture 8: Recap and question session
Wed 26 Apr.  13–15 SP D1.111 Exercise session 4
Exercise sheet
Wed 10 May  13–15 SP D1.111 Lecture 9: Circuit complexity, Karp-Lipton Theorem
Book: Chapter 6
Homework 4
Due: Wed 17 May, 23:59
Thu 11 May  15–17 SP G4.15 Exercise session 5
Exercise sheet
Fri 12 May  15–17 SP G3.02 Lecture 10: Probabilistic algorithms, BPP
Book: 7.1–7.3
Tue 16 May  11–13 SP G3.02 Lecture 11: Approximation, PCP Theorem
Book: 11.0–11.4
Wed 17 May  9–11 SP G0.05 Exercise session 6
Exercise sheet
Wed 17 May  13–15 SP D1.111 Lecture 12: Subexponential-time complexity, Exponential Time Hypothesis
14.0–14.2 of the book Parameterized Algorithms, by Cygan et al.
Wed 24 May  13–15 SP D1.111 Lecture 13: Average-case complexity and Impagliazzo's Five Worlds
Book: 9.0, 9.2, 18.0–18.2, 18.4
(Impagliazzo's paper)
Thu 25 May  15–17 SP G4.15 Exercise session 7
Exercise sheet
Fri 26 May  15–17 SP G3.02 Lecture 14: Recap and question session
Final take-home exam
(Due at Fri 2 Jun., 23:59)
Exams from previous years can be used as practice exams: 2020, 2021.