Lecture and Lab: Complexity Theory

This module gives an introduction to computational complexity theory, the subfield of theoretical computer science that aims at proving lower bounds on the resources (time, memory, randomness, communication) required for solving computational problems. It is aimed at students of mathematics and computer science who are interested in understanding the limits of efficient computation. The course is self-contained. All preliminaries for students from different backgrounds will be included.
Concrete topics in this course include:

- Time and space hierarchy theorems via diagonalization
- NP-completeness and the Cook-Levin theorem
- Space complexity (L, NL, PSPACE)
- The polynomial-time hierarchy and its complete problems
- Communication complexity
- Circuit complexity
- Randomness and derandomization
- Algebraic models of computation

We will show how to use diagonalization to demonstrate complexity separations arising from different resource bounds. Moreover, we will see how to classify problems as polynomial-time solvable or NP-hard via polynomial-time reductions. Besides NP, we will also study the complexity classes L, NL, and PSPACE and their interrelationships and identify complete problems for these classes. Going into complexity classes even harder than NP, we will encounter the polynomial-time hierarchy, identify and recognize problems complete for its various levels, and analyze the consequences of a collapse of this hierarchy. We will show how to exploit randomness as a resource in algorithms and assess techniques and limitations in derandomization of algorithms. Besides Turing machines, we will investigate the role and limitations of circuit complexity in computational complexity. Finally, we will also cast computational problems into algebraic models of computation, such as polynomials and algebraic circuits, and analyze their connections to classical Boolean models of computation.

Time/Date
Tuesday 12-14 (Exercise Wed. 16-18)

Location
BA.607 (Exercise in BA.607)

Link to GRIPS