Computational Complexity
University of Amsterdam – February 2017

Lecturer: Harry Buhrman
Teaching assistant: Tom Bannink
Course catalogue.


Tuesday 13:00-15:00
Thursday 13:00-15:00

Exercise session

Friday 09:00-11:00

For location see Datanose. The first lecture is on Tuesday, February 7 at 13:00 in room SP D1.115.


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

Homework and exam

Exercises will be handed out on Tuesday and have to be handed in on Tuesday one week later. Handing in via email to Tom Bannink is encouraged. You are allowed to cooperate, but everyone has to write down their solution in their own words. When computing the average grade for the exercises, the lowest score will be dropped.

Besides the exercises there will be a final exam. The exam will be open book, which means you are allowed to bring the book and any notes you made – digital equipment is not allowed. The final grade for the course will be the average between the grade for the exercises and the final exam.

If you want to take the resit exam, please send an email to Tom Bannink.


7 Feb.  13-15 SP D1.115 Introduction to computational complexity
Homework 1 Handing in via email is encouraged.
Homework 1 partial solutions
9 Feb.  13-15 SP G2.02 P, NP, reductions, co-NP
Book: 1.1–1.4, 1.6, 1.7, 2.1, 2.2
For visualizations of simple turing machines, you can visit: Online Wolfram Notebook on Turing Machines. In these visualizations, the squares are the tapes and can be white or orange (0 or 1). The small black sign is the 'head' of the Turing Machine which can point up or down which corresponds to the current state of the machine.
10 Feb.  09-11 SP G0.05 Exercise session on asymptotic notations.
Exercises (updated 10 Feb.)
Solutions to the exercises
14 Feb.  13-15 SP D1.115 Cook-Levin Thm: 3-SAT is NP-complete, Decision vs Search
Book: 2.3, 2.5
Homework 2
16 Feb.  13-15 SP G2.02 Diagonalization, time hierarchies
Book: 3.1, 3.2
17 Feb.  09-11 SP G0.05 Exercise session on homework 1.
21 Feb.  13-15 SP D1.115 Relativization
Book: 3.4
Homework 3 (updated 24 Feb.)
Homework 3 partial solutions
23 Feb.  13-15 SP G2.02 Space complexity, PSPACE, L, NL
Book: Chapter 4
24 Feb.  09-11 SP G0.05 Exercise session on homework 2.
28 Feb.  13-15 SP D1.115 Immerman-Szelepcsényi theorem, the polynomial hierarchy
Book: 4.3.2, Chapter 5
Homework 4
2 Mar.  13-15 SP G2.02 Circuit complexity, the Karp-Lipton Theorem
Book: Chapter 6
3 Mar.  09-11 SP G0.05 Exercise session on homework 3.
7 Mar.  13-15 SP D1.115 Parity not in AC^0
Book: 14.2
Homework 5
7 Mar.  13-15 SP G2.02 Probabilistic algorithms
Book: 7.1–7.3
10 Mar.  09-11 SP G0.05 Exercise session on homework 4.
14 Mar.  13-15 SP D1.115 BPP, circuits and polynomial hierarchy
Book: 7.3–7.5
Homework 6
16 Mar.  13-15 SP G2.02 Interactive proofs, Graph-Isomorphism problem
Book: 8.1–8.2
17 Mar.  09-11 SP G0.05 Exercise session on homework 5.
21 Mar.  13-15 SP D1.115 IP = PSPACE
Book: 8.3
23 Mar.  13-15 - No lecture
24 Mar.  09-11 SP G0.05 Exercise session on homework 6.
Question session.
28 Mar. 13-16 SP C1.110 Exam
You are allowed to bring books and notes, but no electronic devices.
Practice exam

See also the website of the 2015/2016 course.