Complexity Theory
Overview
Study of computational resources: time, space. P vs NP is the central open problem. Cook–Levin (1971): SAT is NP-complete. Hierarchy theorems, reductions, completeness.
Era: 1965–1970s
Proposed at: Ithaca, USA (Cornell) / Berkeley, USA
Formal structure
Domain: Language L ⊆ Σ*; Turing machine M; input x, |x| = n
TIME(f) = {L : ∃M deciding L in O(f(n))}; P = ∪_k TIME(n^k); NP = ∃ poly-time verifier
Constraints: Reduction: L ≤_p L' ⟹ L' hard ⇒ L hard; NP-complete: L ∈ NP and ∀L' ∈ NP, L' ≤_p L
Objective: Classify problems; prove P ≠ NP or P = NP
Creators
- Juris Hartmanis
- Richard Stearns
- Stephen Cook
- Leonid Levin
- Richard Karp
- Martin Davis
- Hilary Putnam
- Avi Wigderson
- Silvio Micali