Complexity Theory
From International Center for Computational Logic
Complexity Theory
Lecture series
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
Courses
- Complexity Theory (WS 2024, Markus Krötzsch)
- Complexity Theory (WS 2023, Markus Krötzsch, Stephan Mennicke, Lukas Gerlach)
- Complexity Theory (WS 2022, Markus Krötzsch)
- Complexity Theory (WS 2021, Markus Krötzsch)
- Foundations of Complexity Theory (WS 2020, David Carral)
- Complexity Theory (WS 2019, Markus Krötzsch)
- Complexity Theory (WS 2018, Markus Krötzsch)
- Complexity Theory (WS 2017, Markus Krötzsch)
- Complexity Theory (WS 2015, Markus Krötzsch, Daniel Borchmann)
- Introduction to Complexity Theory (WS 2014, Rafael Peñaloza Nyssen)