Computational Complexity
University of Amsterdam, April–May 2024

Lecturer: Ronald de Haan
Teaching assistants: Wouter Vromen & Hannah Van Santvliet

Course catalogue


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


Thursday 15:00–17:00 (SP A1.28)
Friday 15:00–17:00 (SP A1.04)
(Exceptions are indicated in red in the schedule below.)

Exercise session

Wednesday 13:00–15:00 (SP G0.05)

(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 Tuesdays and have to be handed in on Tuesday 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.


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