Computation Theory · Cluster
Complexity Classes
P, NP, and the landscape of hardness.
- 01 Polynomial Time and the Machine-Independence of P How P is defined by counting steps on a Turing machine, why the class survives a change of machine model, and where the definition stops matching the idea of tractability.
- 02 Certificates and the Two Definitions of NP Why "solved quickly" and "checked quickly" describe the same class, how the verifier definition is proved equivalent to nondeterministic machines, and what the certificate length bound actually constrains.
- 03 Many-One Reductions and What Completeness Requires The mechanics of Karp reductions, why hardness and completeness are different properties, and the closure conditions a class must satisfy for a complete problem to exist.
- 04 The Cook–Levin Tableau: Encoding a Computation as a Formula How a nondeterministic polynomial-time computation becomes a boolean formula whose satisfying assignments correspond exactly to accepting runs, and what the encoding costs in variables and clauses.
- 05 Why Three Literals Is the Pivot for Satisfiability The reduction from general CNF to 3-SAT, why 2-SAT is solvable in linear time while 3-SAT is complete, and how clause length controls the shape of the search space.
- 06 Configuration Graphs and Savitch's Reachability Argument How a nondeterministic space-bounded computation becomes a path problem in a configuration graph, and why reachability composes into a quadratic blowup in space rather than an exponential one.
- 07 Diagonalization and the Time Hierarchy Theorem How a machine that runs itself on its own description separates two time bounds, why the constructibility condition cannot be dropped, and what the theorem does not prove.
- 08 Ladner's Theorem: Building Languages Between P and NP How to construct an NP language that is neither in P nor NP-complete assuming P differs from NP, using a slow diagonalization that delays each requirement until the padding is large enough.
- 09 Oracles, Relativization, and the Limits of Diagonalization How adding an oracle changes what a proof can see, why there are oracles that collapse P and NP and oracles that separate them, and what that implies for any argument that treats machines as black boxes.
- 10 Alternation and the Structure of the Polynomial Hierarchy How stacking existential and universal quantifiers over polynomial-length certificates produces a hierarchy of classes, why it collapses if any two levels coincide, and what complete problems look like at each level.