Lecture: Complexity Theory
Winter term 2016/17 in Braunschweig
The date and room for the exercise class is fixed now. We will already start this week.
The lecture will be given by
Prof. Roland Meyer
Dr. Prakash Saivasan.
Entry in the list of lectures:
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
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:
Lower bounds via crossing sequences. (Week 1)
Time and Space Complexity Classes. (Week 1/2, preliminary)
Alphabet reduction, tape reduction, compression, speed-up. (Week 2, preliminary)
Space vs. time, non-determinism vs. determinism. (Week 3)
Savitch's theorem. (Week 3)
Space and time hierarchy results. (Week 3/4)
Translation theorems. (Week 4)
Immerman and Szelepcsényi's theorem. (Week 4)
Summary of the relationship among the robust complexity classes. (Week 4)
L and NL. (Week 5)
Models of computation for L and NL. (Week 6)
P and NP. (Week 7)
PSPACE. (Week 8)
Alternation. (Week 9)
Alternation (contd.), the polynomial hierarchy. (Week 9)
Oracle Turing machines, relativized complexity classes, and a characterization of the polynomial hierarchy. (Week 10)
Families of Boolean circuits. (Week 11)
Parallel complexity. (Week 12)
Parameterized complexity.(Week 12 & 13)
Hardness in parameterized complexity. (Week 14)
Bounded search trees.
Scheduling and jump number.
Nemhauser and Trotter's theorem.
Hardness in parameterized complexity.
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.
- 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.
- Time Complexity
- Space Complexity
- Savitch's theorem, games
- NL, Immerman and Szlepcseny's theorem
- Hierachy theorems
- Ladner's theorem
- Parameterized Complexity
- Graphs of bounded tree width
- Courcelle's theorem
- Hardness theory
- Polynomial Hierarchy
- Definition and complete problems
- Karp and Lipton's theorem
- Lower bounds
- NC and parallel computing
- Adleman's theorem
- Sipser and Gac's theorem
- Approximate counting
- Toda's theorem
- Communication Complexity
- Logic in Complexity Theory
- Alternative definition of complexity classes
M. Sipser: Introduction to the Theory of Computation.
International Thomson Publishing, 1996
I. Wegener: Complexity Theory.
D.C. Kozen: Automata and Computability.
O. Goldreich: Computational Complexity.