Complexity Theory
The first half of the course covers the basic computational ressources, such as time, parallel time, space and randomness and the associated complexity classes (L, NC, P, BPP, PH, PSPACE, IP etc.) and their relationships.
The second half covers selected topics in complexity theory. Possible topics are the complexity of logical theories, the theory of pseudorandom generators and derandomization and the theory of approximation algorithms including parts of the theory of probabilistically checkable proofs.
Lecturer Peter Bro Miltersen
Literature Christos Papadimitriou: Computational Complexity
Prerequisites dSøgOpt
Lectures 4 hours/week
Course Language English
Evaluation