Lecturer: Harry Buhrman
Teaching assistant: Florian Speelman
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.
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.
Monday 17-19 at D1.162
Wednesday 13-15 at D1.115
Wednesday 15-17 at D1.115
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
|Wednesday, Apr 9||
Diagonalization, time hierarchies |
Book 3.1, 3.2
|Monday, April 14||
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||
The polynomial hierarchy
Book 4.3.2, chapter 5
|Monday, April 28||Circuit complexity, the Karp-Lipton Theorem|
Book chapter 6
|Wednesday, April 30||
Parity not in AC^0 |
|Monday, May 5||No class|
|Wednesday, May 7||
Probabilistic algorithms |
Book 7.1 - 7.3
|Monday, May 12||
BPP, circuits and polynomial hierarchy|
Book 7.3 - 7.5
|Wednesday, May 14||
Interactive proofs, Graph-Isomorphism problem |
Book 8.1 - 8.2
|Monday, May 19||
IP = PSPACE|
|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||
15-18 at Science Park D1.115.
|Wednesday, July 9||
14-17 at Science Park B0.209.