Complexity Theory

Complexity Theory

The first half of the course covers some of the most fundamental results in complexity theory related to the basic complexity classes (L, NC, P, BPP, PH, PSPACE, IP etc.) and to the basic computational ressources, time, parallel time, space and randomness.

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.

The course is commuted through homework every second week.


Lecturer
Erik Meineche Schmidt and Peter Bro Miltersen


Literature


Prerequisites


Course Language


Credits
2 points/10 ECTS-credits