Computational Complexity
University of Amsterdam, February–March 2026
Lecturer: Ronald de Haan
Teaching assistant: Arie Soeteman
Course catalogue
Datanose
Canvas
Textbook
Computational Complexity: A Modern Approach, by Sanjeev Arora and Boaz Barak.
Lectures
Monday 9:00–11:00 (SP D1.114)
Thursday 9:00–11:00 (SP D1.115)
Exercise session
Wednesday 9:00–11:00 (SP G3.02)
(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 (i) the average grade for the exercises and (ii) the final exam.
Schedule
| Time | Location | Topic |
|---|---|---|
| Mon 2 Feb. 9–11 | SP D1.114 | Lecture 1: Introduction to computational complexity Book (core reading): 1.0–1.2, 1.3.0, 1.6 Book (additional reading): 1.2.1, 1.3.1 Slides |
| Wed 4 Feb. 9–11 | SP G3.02 | Exercise session 1
Exercise sheet |
| Thu 5 Feb. 9–11 | SP D1.115 | Lecture 2: P, NP, coNP, reductions Book (core reading): 1.4, 2.0–2.2, 2.6.1 Book (additional reading): 1.7 Slides |
| Mon 9 Feb. 9–11 | SP D1.114 | Lecture 3: NP-completeness, Cook-Levin Theorem, search vs. decision problems Book (core reading): 2.3, 2.5 Book (additional reading): 2.4, 2.7 Slides |
| Homework 1 Due: Tue 17 Feb., 23:59 Use this template (pdf) for typesetting Slitherlink gadgets. See this example solution for an indication of the level of detail required for a good solution. |
||
| Wed 11 Feb. 9–11 | SP G3.02 | Exercise session 2
Exercise sheet |
| Thu 12 Feb. 9–11 | SP D1.115 | Lecture 4: Diagonalization, time hierarchy theorems, Ladner's Theorem Book (core reading): 1.4–1.5, 3.0–3.1 Book (additional reading): 3.2–3.3 Slides |
| Mon 16 Feb. 9–11 | SP D1.114 | Lecture 5: Relativization, Baker-Gill-Solovay Theorem Book (core reading): 3.4.0 Book (additional reading): 3.4.1 Slides |
| Wed 18 Feb. 9–11 | SP G3.02 | Exercise session 3
Exercise sheet |
| Thu 19 Feb. 9–11 | SP D1.115 | Lecture 6: Space complexity, PSPACE, L, NL Book (core reading): 4.0–4.2.1, 4.3.0 Book (additional reading): 4.2.2, 4.3.1–4.3.2 Slides |
| Mon 23 Feb. 9–11 | SP D1.114 | Lecture 7: Polynomial Hierarchy Book (core reading): 5.0–5.3, 5.5 Book (additional reading): 5.4 ('Parody news article' about the collapse of the PH) Slides |
| Homework 2 Due: Thu 5 Mar., 23:59 |
||
| Wed 25 Feb. 9–11 | SP G3.02 | Exercise session 4
Exercise sheet |
| Thu 26 Feb. 9–11 | SP D1.115 | Lecture 8: Circuit complexity, Karp-Lipton Theorem Book (core reading): 6.0–6.1, 6.3–6.4 Book (additional reading): 6.2, 6.5–6.8 Slides |
| Mon 2 Mar. 9–11 | SP D1.114 | Lecture 9: Probabilistic algorithms, BPP Book (core reading): 7.0–7.2.1, 7.3–7.4.1 Book (additional reading): 7.2.2–7.2.4, 7.4.2–7.7 Slides |
| Homework 3 Due: Sun 15 Mar., 23:59 |
||
| Wed 4 Mar. 9–11 | SP G3.02 | Exercise session 5
Exercise sheet |
| Thu 5 Mar. 9–11 | SP D1.115 | Lecture 10: Approximation, PCP Theorem Book (core reading): 11.0–11.2, 11.4 Book (additional reading): 11.3 Slides |
| Mon 9 Mar. 9–11 | SP D1.114 | Lecture 11: Subexponential-time complexity, Exponential Time Hypothesis Core reading: 14.0–14.2 of the book Parameterized Algorithms, by Cygan et al. Slides |
| Wed 11 Mar. 9–11 | SP G3.02 | Exercise session 6
Exercise sheet |
| Thu 12 Mar. 9–11 | SP D1.115 | Lecture 12: Average-case complexity and Impagliazzo's Five Worlds Book (core reading): 9.0, 9.2, 18.0–18.1, 18.4 Book (additional reading): 9.1, 18.2 (Impagliazzo's paper) Slides |
| Mon 16 Mar. 9–11 | SP D1.114 | Lecture 13: Meta Complexity Slides |
| Wed 18 Mar. 9–11 | SP G3.02 | Exercise session 7 Practice exam (exam for 2023) |
| Thu 19 Mar. 9–11 | SP D1.115 | Lecture 14: Recap and question session Slides |
| Final take-home exam
(Due: Fri 27 Mar., 23:59) Exams from past years can be used as practice exams: 2020, 2021, 2023, 2024, 2025. |