Computational Complexity
University of Amsterdam, April–May 2025
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
Tuesday 11:00–13:00 (SP G3.02)
Thursday 15:00–17:00 (SP D1.114)
Exercise session
Tuesday 15:00–17:00 (SP D1.114)
(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 |
|---|---|---|
| Tue 1 Apr. 11–13 | SP G3.02 | 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 |
| Tue 1 Apr. 15–17 | SP D1.114 | Exercise session 1
Exercise sheet |
| Thu 3 Apr. 15–17 | SP D1.114 | Lecture 2: P, NP, coNP, reductions Book (core reading): 1.4, 2.0–2.2, 2.6.1 Book (additional reading): 1.7 Slides |
| Homework 1 Due: Tue 15 Apr., 23:59 Use this template (pdf) for typesetting Slitherlink gadgets. |
||
| Tue 8 Apr. 11–13 | SP G3.02 | 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 |
| Thu 10 Apr. 15–17 | SP D1.114 | 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 |
| Fri 11 Apr. 9–11 | SP D1.115 | Exercise session 2
Exercise sheet |
| Tue 15 Apr. 11–13 | SP G3.02 | Lecture 5: Relativization, Baker-Gill-Solovay Theorem Book (core reading): 3.4.0 Book (additional reading): 3.4.1 Slides |
| Tue 15 Apr. 15–17 | SP D1.114 | Exercise session 3
Exercise sheet |
| Thu 17 Apr. 15–17 | SP D1.114 | 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 |
| Homework 2 Due: Tue 6 May, 23:59 |
||
| Tue 22 Apr. 11–13 | SP G3.02 | 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 |
| Tue 22 Apr. 15–17 | SP D1.114 | Exercise session 4
Exercise sheet |
| Thu 24 Apr. 15–17 | SP D1.114 | 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 |
| Homework 3 Due: Tue 13 May, 23:59 |
||
| Tue 6 May 11–13 | SP G3.02 | 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 |
| Tue 6 May 15–17 | SP D1.114 | Exercise session 5
Exercise sheet |
| Thu 8 May 15–17 | SP D1.114 | Lecture 10: Approximation, PCP Theorem Book (core reading): 11.0–11.2, 11.4 Book (additional reading): 11.3 Slides |
| Tue 13 May 11–13 | SP G3.02 | Lecture 11: Subexponential-time complexity, Exponential Time Hypothesis Core reading: 14.0–14.2 of the book Parameterized Algorithms, by Cygan et al. Slides |
| Tue 13 May 15–17 | SP D1.114 | Exercise session 6
Practice exam (exam for 2023) |
| Thu 15 May 15–17 | SP D1.114 | Lecture 12: Average-case complexity and Impagliazzo's Five Worlds Book (core reading): 9.0, 9.2, 18.0–18.1, 18.4 Bookk (additional reading): 9.1, 18.2 (Impagliazzo's paper) Slides |
| Tue 20 May 11–13 | SP G3.02 | Lecture 13: Recap and question session
Slides |
| Final take-home exam
(Due: Wed 28 May, 23:59) Exams from past years can be used as practice exams: 2020, 2021, 2023, 2024. |