The objective of complexity theory is to classify computational problems according to the inherent amount of resources needed to solve them and to group problems with similar needs 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 one of the most significant open questions in theoretical computer science, and even 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 randomized algorithms, among others.
The lecture aims at giving a broad overview of the basic concepts and results of complexity theory:
- Classical results for space and time complexity classes: e.g., basic relationships 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
- Basic complexity theory of randomized 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.
- Kursleiter/in: Marko Schmellenkamp
- Kursleiter/in: Thomas Zeume