Table of contents

Computational Complexity Theory

A graduate-level path from formal models to modern complexity classes, reductions, lower bounds, randomness, circuits, communication, proof systems, and quantum complexity

Read each section in order. Every title can be opened as a TheoryTrace document.

• Cover
• Copyright
• How to read this book
• Introduction
• Chapter 1: What Complexity Theory Studies
• Chapter 2: Models of Computation and Robustness
• Chapter 3: Time, Space, and Complexity Classes
• Chapter 4: Reductions and Completeness
• Chapter 5: Nondeterminism and NP
• Chapter 6: NP-Completeness
• Chapter 7: Beyond NP: coNP, DP, and the Polynomial Hierarchy
• Chapter 8: Diagonalization and Hierarchy Theorems
• Chapter 9: Space Complexity and Savitch’s Theorem
• Chapter 10: PSPACE, Games, and Alternation
• Chapter 11: Circuit Complexity
• Chapter 12: Circuit Lower Bounds and Barriers
• Chapter 13: Randomized Computation
• Chapter 14: Counting Complexity
• Chapter 15: Interactive Proofs and Probabilistically Checkable Proofs
• Chapter 16: Hardness of Approximation
• Chapter 17: Communication Complexity
• Chapter 18: Descriptive Complexity and Logic
• Chapter 19: Pseudorandomness and Derandomization
• Chapter 20: Average-Case Complexity and One-Way Functions
• Chapter 21: Fine-Grained Complexity
• Chapter 22: Parameterized Complexity
• Chapter 23: Quantum Complexity Theory
• Chapter 24: The Landscape of Open Problems
• Conclusion