Contents
Computational complexity theory aims to classify computational problems according to the algorithmic resources required for their solution. Resources are for example time, space, nondeterminism, or randomness. A central role is played by the class P of problems solvable in polynomial time. The central problem is the P versus NP problem, one of the Clay institute's millenium problems of mathematics, and, according to Smale, one of the three greatest open problems of mathematics. The course offers an introduction to this problem and its surrounding theory.
Continuously updated lecture notes on StudIP.
Lectures
Tuesday 12:00-14:00 IM SR030
Wednesday 10:00-12:00 JUR HS12
Exercises by Johannes Heil
Thursday 10:00-12:00 JUR SR 154
Literature
Arora, Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 2009. Draft
Papadimitriou, Computational Complexity, Addison-Wesley, 1995.
This is an advanced seminar joint with Tobias Kaiser. It offers research talks of the respective groups and their visitors. Advanced students who wish to deepen their knowledge in mathematical logic and/or complexity theory can give talks on jointly chosen and jointly elaborated topics.
Program pdf
