Complexity Classes & Cook's Theorem — Summary

(i) $P$, $NP$, $NP$-Complete, $NP$-Hard (as in Q22)

• $P$: polytime solvable deterministic — tractable.
• $NP$: polytime verifiable (nondet polytime). $P\subseteq NP$.
• $NP$-Hard: every $NP$ ≤$_p$ it.
• $NP$-Complete: $NP$-Hard ∩ $NP$ — hardest in $NP$.

(ii) Cook's Theorem

SAT (and 3-SAT) is NP-complete. Statement: For any $L∈NP$ with nondet TM $M$ running in $p(n)$, there is polytime construction $x↦ φ_x$ poly-size CNF such that $x∈L ⇔ φ_x$ satisfiable. See Q86 proof sketch (tableau encoding). Converse SAT∈NP via assignment verifier.

(iii) Why Foundational

• First NP-complete problem — provides base for all NP-completeness reductions (Karp's 21 problems).
• Establishes existence of hardest NP problems; implies $P=NP$ iff SAT∈$P$.
• Launched theory of NP-completeness, guiding algorithm design (choose approximation/heuristic when NP-hard).
• Connects logic, computation, and combinatorics; Levin independently discovered similar (Cook-Levin theorem).
• Practical: SAT solvers despite NP-completeness handle huge instances (industrial use).