Lecturer: Harry Buhrman
Teaching assistant: Tom Bannink
Course catalogue.
Datanose
Tuesday 13:0015:00
Thursday 13:0015:00
Friday 09:0011:00
For location see Datanose. The first lecture is on Tuesday, February 7 at 13:00 in room SP D1.115.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.
Time  Location  Topic 

7 Feb. 1315  SP D1.115  Introduction to computational complexity Homework 1 Handing in via email is encouraged. Homework 1 partial solutions Slides 
9 Feb. 1315  SP G2.02  P, NP, reductions, coNP 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. 0911  SP G0.05  Exercise session on asymptotic notations. Exercises (updated 10 Feb.) Solutions to the exercises 
14 Feb. 1315  SP D1.115  CookLevin Thm: 3SAT is NPcomplete, Decision vs Search Book: 2.3, 2.5 Homework 2 
16 Feb. 1315  SP G2.02  Diagonalization, time hierarchies Book: 3.1, 3.2 
17 Feb. 0911  SP G0.05  Exercise session on homework 1. 
21 Feb. 1315  SP D1.115  Relativization Book: 3.4 Homework 3 (updated 24 Feb.) Homework 3 partial solutions 
23 Feb. 1315  SP G2.02  Space complexity, PSPACE, L, NL Book: Chapter 4 
24 Feb. 0911  SP G0.05  Exercise session on homework 2. 
28 Feb. 1315  SP D1.115  ImmermanSzelepcsényi theorem, the polynomial hierarchy Book: 4.3.2, Chapter 5 Homework 4 
2 Mar. 1315  SP G2.02  Circuit complexity, the KarpLipton Theorem Book: Chapter 6 
3 Mar. 0911  SP G0.05  Exercise session on homework 3. 
7 Mar. 1315  SP D1.115  Parity not in AC^0 Book: 14.2 Homework 5 
7 Mar. 1315  SP G2.02  Probabilistic algorithms Book: 7.1–7.3 
10 Mar. 0911  SP G0.05  Exercise session on homework 4. 
14 Mar. 1315  SP D1.115  BPP, circuits and polynomial hierarchy Book: 7.3–7.5 Homework 6 
16 Mar. 1315  SP G2.02  Interactive proofs, GraphIsomorphism problem Book: 8.1–8.2 
17 Mar. 0911  SP G0.05  Exercise session on homework 5. 
21 Mar. 1315  SP D1.115  IP = PSPACE Book: 8.3 
23 Mar. 1315    No lecture 
24 Mar. 0911  SP G0.05  Exercise session on homework 6. Question session. 
28 Mar. 1316  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.