Complexity Theory
The first half of the course covers some of the most fundamental results in complexity theory related to the basic complexity classes (Logspace, NC, P, IP/Pspace etc.) and to the basic computational ressources, time and space.
The second half is concerned with complexity of logical theories and the theory of approximation algorithms including (parts of) the theory of probabilistically checkable proofs (PCP).
"Afløsning": Homework every second week.
Lecturer
Erik Meineche Schmidt
Literature
Dexter Kozen: Lectures on the Theory of Computing (manuscript), and other course notes
Prerequisites
Algorithmics 1
Course Language
Danish or English
Credits
2 points/10 ECTS-credits