Theoretical Computer Science

Lecture: Complexity Theory

Winter term 2016/17 in Braunschweig

News

• The date and room for the exercise class is fixed now. We will already start this week.

Organisation

• The lecture will be given by Prof. Roland Meyer and Dr. Prakash Saivasan.
• Entry in the list of lectures: Lecture, Exercises.
• The dates and rooms for the lecture are:
  • Mondays, 09:45 - 11:15 in SN 19.3
  • Tuesdays, 16:45 - 18:15 in SN 19.7
• The date and room for the exercise class:
  • Wednesday, 11:30 - 12:45 in room 358, the Institute for Theoretical Computer Science, Muehlenpfordstrasse 22-23

Lecture Notes

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

• Download Exercise Sheet 1 here.
• Download Exercise Sheet 2 here.
• Download Exercise Sheet 3 here.
• Download Exercise Sheet 4 here.
• Download Exercise Sheet 5 here.
• Download Exercise Sheet 6 here.
• Download Exercise Sheet 7 here.
• Download Exercise Sheet 8 here.
• Download Exercise Sheet 9 here.

Content:

• Time Complexity
  • P, NP, NP-completeness
• Space Complexity
  • Savitch's theorem, games
  • NL, Immerman and Szlepcseny's theorem
• Diagonalization
  • Hierachy theorems
  • Ladner's theorem
• Parameterized Complexity
  • Graphs of bounded tree width
  • Courcelle's theorem
  • Hardness theory
• Polynomial Hierarchy
  • Definition and complete problems
  • Alternation
  • Collapse
• Circuits
  • P/poly
  • Karp and Lipton's theorem
  • Lower bounds
  • NC and parallel computing
• Randomness
  • BPP
  • Adleman's theorem
  • Sipser and Gac's theorem
• Counting
  • #P
  • Approximate counting
  • Toda's theorem
• Communication Complexity
  • Fooling sets
• Logic in Complexity Theory
  • Alternative definition of complexity classes
  • Theories

Literature:

• M. Sipser: Introduction to the Theory of Computation. International Thomson Publishing, 1996
• I. Wegener: Complexity Theory. Springer, 2005
• D.C. Kozen: Automata and Computability. Springer, 1997
• O. Goldreich: Computational Complexity. Cambridge, 2008