Computational Complexity
University of Amsterdam, April–May 2023
Lecturer: Ronald de Haan
Teaching assistants: Martijn Brehm & Jana Sotáková
Course catalogue
Datanose
Canvas
Textbook
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.
Schedule
| Time | Location | Topic |
|---|---|---|
| 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 https://turingmachinesimulator.com/ (the Turing machines shown there are bidirectional, see Claim 1.8 in the book). Slides |
| 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 Slides |
| 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 Slides |
| 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 Slides |
| Wed 19 Apr. 13–15 | SP D1.111 | Lecture 5: Relativization, Baker-Gill-Solovay Theorem Book: 3.4 Slides |
| 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 Slides |
| Tue 25 Apr. 11–13 | SP G3.02 | Lecture 7: Polynomial Hierarchy Book: Chapter 5 ('Parody news article' about the collapse of the PH) Slides |
| Homework 3 Due: Wed 10 May, 23:59 |
||
| Wed 26 Apr. 9–11 | SP G4.15 | Lecture 8: Recap and question session
Slides |
| 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 Slides |
| 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 Slides |
| Tue 16 May 11–13 | SP G3.02 | Lecture 11: Approximation, PCP Theorem Book: 11.0–11.4 Slides |
| 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. Slides |
| 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 Slides (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
Slides |
| Final take-home exam
(Due at Fri 2 Jun., 23:59) Exams from previous years can be used as practice exams: 2020, 2021. |