Complexity Theory

Complexity Theory

Complexity Theory

The course starts with a discussion of different computing models and compares their computational power. It continues with a brief introduction to the necessary theory of logic (mainly propositional and first order logic).

The course continues with a number of fundamental results in complexity theory, including hierarchy results and results on the relation between different computational ressources (in particular time and space). Then follows complexity of logical theories and (parts of) the theory of approximation.

LecturerErik Meineche Schmidt

LiteratureC. H. Papadimitriou: "Computational Complexity", Addison-Wesley, 1994, and course notes.

PrerequisitesAlgorithmics 1