• Lecturer: Prof. Dr. Zeume
• Language: English
• Credits: 9 CP
• Programs: M.Sc. Mathematics, M.Sc. IT-Security, M.Sc. Applied Computer Science, M.Sc. Computer Science
• Examination: 100 % Oral Exam (30 Minutes) + 10 % Homework

Prior Knowledge

Basic Knowledge of Theoretical Computer Science

Learning Outcomes

Students learn to categorize algorithmic problems in terms of their complexity and thus identify suitable algorithmic techniques to solve them. In particular, they can apply algorithmic methods for NP-complete problems. They can deal with different calculation models and can prove simple statements about them. They learn to evaluate their own and others’ solution approaches in discourse.

Course Description

Complexity theory examines and classifies computational problems in terms of their algorithmic difficulty. The goal is to determine the inherent resource consumption with respect to different resources such as computing time or space, and to group problems with similar resource consumption into complexity classes. The best known complexity classes are certainly P and NP, which comprise the problems that can be solved and verified in polynomial time, respectively. The question of whether P and NP are distinct is considered to be one of the most important open questions in theoretical computer science, even in mathematics. However, P and NP are only two examples of complexity classes. Other classes arise, among others, in the investigatino of the required memory space, the efficient parallelizability of problems, the solvability by random algorithms, and the approximate solvability of problems. 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. the correspondence between games and memory constraints, the proof that with more space or time one can also solve more problems, other fundamental relationships between time and space-based classes, and the complexity world between NP and PSPACE
• Basic complexity theory of parallel, random, and approximate algorithms
• Introduction to selected recent topics: Complexity theory of interactive computing, of probabilistic reasoning, and fine-grained complexity

Contents

Part A: Classic complexity classes

1. Spaces and puzzles
2. Alternation and games
3. Exponential time and time hierarchy
4. Space and reachability Part B: Complexity classes below PTIME
5. Parallel complexity classes and circuits
6. Efficient parallelizability
7. The computational power of constant-depth circuits
8. Barriers for the computational power of circuits Part C: Between PTIME and PSPACE
9. The polynomial time hierarchy
10. Probabilistic complexity classes
11. Counting complexity classes
12. Between PTIME and NP Interlude: Logic & computational complexity Part D: From complexity theory to algorithms
13. Approximation algorithms & complexity theory
14. Parameterized algorithms
15. Parameterized complexity theory
16. Fine-grained complexity theory Interlude: Communication complexity Part E: Interactive computations
17. Interactive proof systems
18. Artur-Merlin proof systems
19. Probabilistically checkable proofs: Introduction
20. Probabilistically checkable proofs: Proof of the small PCP theorem
21. (Introduction to) Cryptography and zero-knowledge proofs