Computational Complexity - University of Amsterdam

April - June 2014, course code 5314COCO6Y

Lecturer: Harry Buhrman

Teaching assistant: Florian Speelman

Grades are out

You can find your grades on blackboard. Most of you made it, good job! Please send us an e-mail if you do not find your grade there, or have trouble accessing blackboard.

Resit exam

There will be a resit, date and time: Wednesday July 9th, 14:00-17:00 at Science Park B0.209.
Please send us an e-mail if you want to participate in the resit.


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

Time and location


Monday 17-19 at D1.162
Wednesday 13-15 at D1.115

Exercise session:

Wednesday 15-17 at D1.115

Homework and exam

Exercises will be handed out every week, they should be handed in at the start of the Monday lecture of the next week. The solutions should either be handed in by paper (handwritten is fine), or sent by email to Florian. 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 also be a final exam on May 26th. 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 calculated as the average between the grade for the exercises and the final exam.

Previous year's exam is available online. Don't forget that the exact topics tested (and exam size) will not necessarily be the same this year!


Monday, Mar 31 Introduction to computational complexity

Homework #1 (Exercise 4 updated on April 2! Also slight rewording of Exercise 3 on April 3.)
Wednesday, April 2 P, NP, reductions, co-NP
Book 1.1-1.4, 1.6, 1.7, 2.1, 2.2
Exercises to solve in class
Monday, April 7 Cook-Levin Thm: 3-SAT is NP-complete, Decision vs Search
Book 2.3, 2.5

Homework #2
Wednesday, Apr 9 Diagonalization, time hierarchies
Book 3.1, 3.2
Monday, April 14 Relativization
Book 3.4

Homework #3 (Clarification of definition 1.(II) on April 17.)
Wednesday, April 16 Space complexity, PSPACE, L, NL
Book chapter 4
Monday, Apr 21 No class
Wednesday, April 23 Immerman-Szelepcsényi theorem
The polynomial hierarchy
Book 4.3.2, chapter 5

Homework #4
Monday, April 28 Circuit complexity, the Karp-Lipton Theorem
Book chapter 6

Homework #5
Wednesday, April 30 Parity not in AC^0
Book 14.2
Monday, May 5 No class
Wednesday, May 7 Probabilistic algorithms
Book 7.1 - 7.3

Homework #6
Monday, May 12 BPP, circuits and polynomial hierarchy
Book 7.3 - 7.5

Homework #7
Wednesday, May 14 Interactive proofs, Graph-Isomorphism problem
Book 8.1 - 8.2
Monday, May 19 IP = PSPACE
Book 8.3
Wednesday, May 21 Final exercise session & any questions you might have (Florian)

Class starts at 13:00, which means we'll finish a bit earlier than normal.
Monday, May 26 Final exam
15-18 at Science Park D1.115.
Wednesday, July 9 Exam resit
14-17 at Science Park B0.209.