Description
The lecture is concerned with the theory of computational
complexity. We assume familiarity with the basics of computability
theory and complexity theory as provided by
Discrete Mathematics and
Formal Languages and Automata Theory.
| week 1: |
The Complexity of Computations |
| week 2: |
Time and Space Complexity Classes and Savitch's Theorem
|
| week 3: |
Separation Results
|
| week 4: |
The Immerman Szelepcsenyi Theorem
|
| week 5: |
Logspace Computability
|
| week 6: |
The Circuit Value Problem
|
| week 7: |
Alternation
|
| week 8: |
Problems Complete for PSPACE
|
| week 9: |
The Polynomial Time Hierarchy
|
| week 10: |
More on the Polynomial Time Hierarchy
|
| week 11: |
Parallel Complexity
|
| week 12: |
Relation of NC to Time-Space Classes
|
| week 13: |
Probabilistic Complexity
|
| week 14: |
Interactive Proofs
|
Literature
The lecture will follow Kozen's book quite closely.
- Theory of Computation, Dexter C. Kozen,
426 pages, Springer, 1 edition (March 23, 2006)
ISBN 1846282977
Language
The course will be held in English.