Computational Complexity Theory

Graduate Course, Ruhr University Bochum, 2022

  • 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


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