Institute of

Theoretical Computer Science


Technische Universität Braunschweig

Complexity Theory 2015/2016



Dates and rooms:


There will be an oral exam on the contents of the lecture. To be admitted to the exam, you have to fulfil the following requirements:
  1. 60 percent of your exercises have to be marked by a plus.
  2. You have to present some of your exercise solutions on the board .
Prof. Meyer offers an exam date on Friday, March 11, and at least one exam date in the middle of April (presumably April 14/15).

To get a fixed date for your oral exam, please write an e-mail to Peter Chini. Mention your full name, the lecture for which you want to do the exam and your preferred date (11.03 or mid of April) in the e-mail. If you prefer to have your exam in the morning or in the afternoon, you can also mention this.

Don't forget to register the exam with the Prüfungsamt (examination office) as soon as the date is fixed.

Lecture Notes

There are handwritten notes on the topics of the lecture:
  1. Lower bounds via crossing sequences. (Week 1)
  2. Time and Space Complexity Classes. (Week 1/2, preliminary)
  3. Alphabet reduction, tape reduction, compression, speed-up. (Week 2, preliminary)
  4. Space vs. time, non-determinism vs. determinism. (Week 3)
  5. Savitch's theorem. (Week 3)
  6. Space and time hierarchy results. (Week 3/4)
  7. Translation theorems. (Week 4)
  8. Immerman and Szelepcsényi's theorem. (Week 4)
  9. Summary of the relationship among the robust complexity classes. (Week 4, update)
  10. L and NL. (Week 5)
  11. Models of computation for L and NL. (Week 6)
  12. P and NP. (Week 7)
  13. PSPACE. (Week 8)
  14. Alternation. (Week 9)
  15. Alternation (contd.), the polynomial hierarchy. (Week 9)
  16. Oracle Turing machines, relativized complexity classes, and a characterization of the polynomial hierarchy. (Week 10)
  17. Ladner's theorem, diagonalization and its limits. (Week 11)
  18. Families of Boolean circuits. (Week 12)
  19. Parallel complexity. (Week 12)
  20. Non-uniform polynomial time. (Week 13)
  21. Parameterized complexity. (Week 13)
  22. Bounded search trees. (Week 13)
  23. Scheduling and jump number. (Week 14)
  24. Kernelization. (Week 14)
  25. Nemhauser and Trotter's theorem. (Week 15)
  26. Iterative compression. (Week 15)
  27. Hardness in parameterized complexity. (Week 16)
  28. Advanced topics in parameterized complexity. (Week 16)


Exercises will be made available here on Wednesday evenings. Please hand in your solution in groups of 3 to 4 people in the box in building 34, 4th floor, close to room 401 and the SoftTech AG. If you have questions or encounter problems with the exercises, please contact Peter.