en | de

Komplexitätstheorie

Masterstudium

VO2.5  SS 2008  703751

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.

Language

The course will be held in English.