Institute of

Theoretical Computer Science


Technische Universität Braunschweig

Lecture: Complexity Theory

Winter term 2016/17 in Braunschweig



Lecture Notes

There is a script (27.10.2016) that is updated on a regular basis. Moreover, there are handwritten notes on the topics of the course:
  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)
  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. Families of Boolean circuits. (Week 11)
  18. Parallel complexity. (Week 12)
  19. Parameterized complexity.(Week 12 & 13)
  20. Hardness in parameterized complexity. (Week 14)

Additional Material

  1. Parameterized complexity.
  2. Bounded search trees.
  3. Scheduling and jump number.
  4. Kernelization.
  5. Nemhauser and Trotter's theorem.
  6. Iterative compression.
  7. Hardness in parameterized complexity.
  8. Advanced topics in parameterized complexity.


Exercises will be made available here on Tuesday after the lecture. Please hand in your solution in groups of 2 to 3 people in the box besides room 343 in the Institute for Theoretical Computer Science, Muehlenpfordstrasse 22-23. If you have questions or encounter problems with the exercises, please contact Prakash Saivasan.