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