Complexity Theory

This course covers the fundamental concepts as well as advanced topics of complexity theory.

Key topics are:

Turing Machines (revision): Definition of Turing Machines; Variants; Computational Equivalence; Decidability and Recognizability; Enumeration
Undecidability: Examples of Undecidable Problems; Mapping Reductions; Rice’s Theorem (both for characterizing Decidability and Recognizability); Recursion Theorem; Outlook into Decidability in Logic
Time Complexity: Measuring Time Complexity; Many-One Reductions; Cook-Levin Theorem; Time Complexity Classes (P, NP, ExpTime); NP-completeness; pseudo-NP-complete problems
Space Complexity: Space Complexity Classes (PSpace, L, NL); Savitch’s Theorem; PSpace-completeness; NL-completeness; NL = coNL
Diagonalization: Hierarchy Theorems (det. Time, non-det. Time, Space); Gap Theorem; Ladner’s Theorem; Relativization; Baker-Gill-Solovay Theorem
Alternation: Alternating Turing Machines; APTime = PSpace; APSpace = ExpTime; Polynomial Hierarchy
Circuit Complexity: Boolean Circuits; Alternative Proof of Cook-Levin Theorem; Parallel Computation (NC); P-completeness; P/poly; (Karp-Lipton Theorem, Meyer’s Theorem)
Probabilistic Computation: Randomized Complexity Classes (RP, PP, BPP, ZPP); Sipser-Gács-Lautemann Theorem
Quantum Computing: Quantum circuits, BQP, some basic results