# 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

# Contents

Part A: Classic complexity classes

- Spaces and puzzles
- Alternation and games
- Exponential time and time hierarchy
- Space and reachability Part B: Complexity classes below PTIME
- Parallel complexity classes and circuits
- Efficient parallelizability
- The computational power of constant-depth circuits
- Barriers for the computational power of circuits Part C: Between PTIME and PSPACE
- The polynomial time hierarchy
- Probabilistic complexity classes
- Counting complexity classes
- Between PTIME and NP Interlude: Logic & computational complexity Part D: From complexity theory to algorithms
- Approximation algorithms & complexity theory
- Parameterized algorithms
- Parameterized complexity theory
- Fine-grained complexity theory Interlude: Communication complexity Part E: Interactive computations
- Interactive proof systems
- Artur-Merlin proof systems
- Probabilistically checkable proofs: Introduction
- Probabilistically checkable proofs: Proof of the small PCP theorem
- (Introduction to) Cryptography and zero-knowledge proofs