Informations du cours

The goal of complexity theory is to classify computational problems according to the inherent amount of resources required to solve them and to group problems with similar resource requirements into complexity classes.  The best known complexity classes are certainly P and NP, which comprise the problems that can be solved and verified, respectively, in polynomial time. The question of whether P and NP are distinct is considered to be one of the most important open questions in theoretical computer science and mathematics. However, P and NP are only two examples of complexity classes. Other classes arise in the study of required space, efficient parallelizability of problems, and solvability by randomised algorithms, among others.

The lecture aims to give a broad overview of the basic concepts and results of complexity theory:

• Classical results for space and time complexity classes: e.g., basic relations between time and space-based classes, the proof that more problems can be solved when more space or time is available, connections between classical complexity classes and games, and the complexity world between NP and PSPACE
• Fundamental complexity theory of randomised and parallel algorithms
• Other selected topics: Complexity theory of interactive computations; probabilistic, interactive proof systems; and fine-grained complexity

This course is intended for students of computer science and mathematics.

Prerequisites:

• Successful completion of a basic course on theoretical computer science (formal languages, basics of complexity theory including NP-completeness and reductions, basics of computability theory)

Introductory literature for this course:

• Arora, Barak. Computational Complexity: A Modern Approach. Cambridge University Press. A preprint is available at: http://theory.cs.princeton.edu/complexity/book.pdf
• Papadimitriou. Computational Complexity. Addison-Wesley. Reading. 1995.
• Kozen. Theory of Computation. Springer. 2006.
• Wegener. Komplexitätstheorie: Grenzen der Effizienz von Algorithmen. Springer. 2003.

Learning outcomes

Students learn to classify algorithmic problems with respect to their complexity and to identify suitable algorithmic techniques for their solution. They can, in particular, apply algorithmic methods for NP-complete problems, deal with different computational models and are able to prove simple statements about them. They learn how to evaluate approaches in the discourse with other students.