Complexity Theory: P, NP, and NP-Completeness

⚡ Key Takeaways

P vs NP asks whether every problem whose solution can be verified quickly can also be solved quickly. P is the class of problems solvable in polynomial time; NP is the class of problems whose proposed solutions are verifiable in polynomial time. An NP-complete problem is a "hardest" problem in NP: if any one of them has a polynomial-time algorithm, then P = NP. The question was crystallized by Stephen Cook (1971) and Leonid Levin (1973); it remains the central open problem of theoretical computer science and one of the seven Clay Millennium Prize Problems.

💡 The Core Insight

Verification may be easier than discovery. Finding a solution to a hard problem (a satisfying assignment, a Hamiltonian cycle, a valid Sudoku fill) seems to require searching an exponential space, but checking a proposed solution is trivial. P vs NP asks whether this asymmetry is real or illusory. Reductions are the tool that ties problems together: if problem $A$ can be transformed into problem $B$ in polynomial time, then $B$ is "at least as hard" as $A$ . NP-completeness identifies the problems to which all of NP reduces — the apex of difficulty within NP.

DefinitionThe Class P

A language $L$ is in P (Polynomial time) if there exists a deterministic Turing machine $M$ and a constant $k$ such that $M$ decides $L$ and, on every input $x$ , halts within $O(|x|^k)$ steps:

1

\quad \mathrm{P} = \bigcup_{k \ge 1} \mathrm{DTIME}\!\left(n^{k}\right)

where $n = |x|$ is the input length, and $\mathrm{DTIME}(f(n))$ is the set of languages decidable by a DTM in $O(f(n))$ time.

DefinitionThe Class NP

A language $L$ is in NP (Nondeterministic Polynomial time) if there exists a polynomial-time deterministic "verifier" $V(x, c)$ and a polynomial $p$ such that:

2

\quad x \in L \;\iff\; \exists\, c \in \Sigma^{*},\; |c| \le p(|x|) \;\text{ and }\; V(x,c) = 1

Here $c$ is the certificate (or witness), and $V$ runs in time polynomial in $|x|$ . Equivalently, $\mathrm{NP} = \bigcup_{k} \mathrm{NTIME}(n^k)$ , the class decidable by a nondeterministic TM in polynomial time.

DefinitionPolynomial-Time Many-One Reduction

A language $A$ reduces to $B$ (written $A \le_p B$ ) if there is a polynomial-time computable function $f : \Sigma^* \to \Sigma^*$ such that:

3

\quad \forall x:\quad x \in A \;\iff\; f(x) \in B

The function $f$ is the reduction. Intuitively, an efficient algorithm for $B$ yields an efficient algorithm for $A$ via $A\text{-instance} \xrightarrow{f} B\text{-instance} \to \text{solve } B$ .

DefinitionNP-Hardness and NP-Completeness

A language $B$ is NP-hard if every $A \in \mathrm{NP}$ satisfies $A \le_p B$ . A language $B$ is NP-complete if it is both NP-hard and a member of NP:

4

\quad B \text{ is NP-complete} \;\iff\; B \in \mathrm{NP} \;\wedge\; \big(\forall A \in \mathrm{NP}:\; A \le_p B\big)

TheoremCook–Levin Theorem

The Boolean satisfiability problem (SAT) — given a Boolean formula $\varphi$ , does there exist an assignment of truth values making $\varphi$ true? — is NP-complete. Consequently, the following are equivalent: 1. $\mathrm{P} = \mathrm{NP}$ . 2. SAT $\in$ P. 3. Some (equivalently, every) NP-complete problem is in P.

ProofSketch of Cook–Levin

We must show (a) SAT $\in$ NP and (b) every $L \in$ NP reduces to SAT.

Step 1 — SAT $\in$ NP. Given formula $\varphi$ , a certificate is a satisfying assignment $c$ . The verifier substitutes $c$ and evaluates $\varphi$ , which takes time linear in $|\varphi|$ . Thus SAT $\in$ NP by [2].

Step 2 — Setup for hardness. Let $L \in$ NP, decided by a nondeterministic TM $M$ that on input $x$ runs in $\le n^k$ steps, where $n=|x|$ . The full execution of $M$ can be laid out in a tableau: a table of $(n^k+1) \times (n^k+1)$ cells, row $i$ describing the configuration of $M$ at time $i$ (tape contents, head position, state).

Step 3 — Variables. Introduce Boolean variables $T_{i,j,s}$ meaning "cell $(i,j)$ holds symbol $s$ ." There are polynomially many variables since the tableau is polynomial in size.

Step 4 — Constraints as clauses. Build a formula $\varphi_x = \varphi_{\text{cell}} \wedge \varphi_{\text{start}} \wedge \varphi_{\text{accept}} \wedge \varphi_{\text{move}}$ :

$\varphi_{\text{cell}}$ : each cell holds exactly one symbol.
$\varphi_{\text{start}}$ : row 0 encodes the initial configuration on input $x$ .
$\varphi_{\text{accept}}$ : some row contains the accept state.
$\varphi_{\text{move}}$ : every $2\times 3$ "window" of adjacent cells is consistent with $M$ 's transition function. This is the key local-checkability step.

Step 5 — Correctness. $\varphi_x$ is satisfiable iff there is a valid accepting computation of $M$ on $x$ , i.e. iff $x \in L$ . By [3] this is a polynomial-time reduction $L \le_p \mathrm{SAT}$ , since each piece of $\varphi_x$ has polynomial size and is constructible in polynomial time. Hence SAT is NP-hard, and with Step 1, NP-complete. $\blacksquare$

∎

mathematician · Stephen Cook | b. 1939

Stephen Arthur Cook, a logician at the University of Toronto, presented "The Complexity of Theorem-Proving Procedures" at the 1971 ACM STOC, defining NP-completeness and proving SAT complete. Independently, Leonid Levin (then in Moscow, later at Boston University) discovered essentially the same notion (his "universal search problems") around 1973. Cook received the 1982 Turing Award for founding computational complexity theory's central question. The pairing is honored in the name Cook–Levin theorem.

🧠 Intuition

Think of NP as the class of problems where a clever oracle could hand you a proof of a "yes" answer that you can check on the back of an envelope.

A jigsaw puzzle: assembling it is hard, but if someone shows you the completed picture, verifying it's correct is easy. That's NP.
A maze: finding the exit may take exponential search; checking a given path is trivial.
NP-completeness is like discovering that every puzzle in the universe is secretly the same puzzle in disguise — solve one efficiently and you've solved all of them.

The word "nondeterministic" is a historical name; modern intuition prefers the certificate picture. NP is not "exponential time" — it sits between P and EXPTIME and we do not know exactly where. The deep mystery: searching feels exponential, but no one has proven it must be.

TV

The verification asymmetry

A useful mental model is energy landscapes: P problems are like convex bowls (roll downhill to the minimum), while NP-complete problems resemble rugged glassy landscapes with exponentially many local minima — finding the global optimum requires exploring exponentially many valleys, yet recognizing the bottom once you're there is instant. Statistical-mechanics methods (spin glasses, the replica method) have even predicted phase transitions in random SAT: as the clause-to-variable ratio crosses $\alpha \approx 4.267$ for random 3-SAT, instances flip sharply from almost-always-satisfiable to almost-always-unsatisfiable, with the hardest instances clustered at the threshold.

ExampleVerifying a certificate puts a problem in NP

Problem (SUBSET-SUM): Given integers $S = \{3, 7, 12, 19, 21\}$ and target $t = 30$ , is there a subset summing to $t$ ?

Given: 5 numbers; the search space has $2^5 = 32$ subsets.

As a search: brute force checks up to 32 subsets.

As verification (NP): Suppose a certificate $c = \{7, 12, 19\}$ ... wait, $7+12+19 = 38 \ne 30$ . Try $c = \{3, 7, 21\}$ instead.

Step 1: Check $c \subseteq S$ : yes, $\{3,7,21\}\subseteq S$ . ✓
Step 2: Sum the elements: $3 + 7 + 21 = 31$ . ✗ — not 30.
Try $c = \{12, 19\}$ : $12 + 19 = 31$ . ✗
Try $c = \{3, 7, 19\}$ ? wait $3+7+19=29$ . ✗ Try $\{3,...\}$ : actually $\{12,19\}=31$ , $\{7,12,...\}$ .... Let us test the true witness $c=\{3,7,...\}$ . By exhaustion the achievable sums near 30 are 31 ( $\{12,19\}$ , $\{3,7,21\}$ ) and 29 ( $\{3,7,19\}$ ); no subset sums to exactly 30.

Verification cost: each check is one summation of $\le 5$ numbers — $O(n)$ time, independent of the $2^n$ search.

\boxed{\text{SUBSET-SUM} \in \mathrm{NP};\ \text{here the answer is NO (no certificate exists).}}

ExampleA polynomial-time reduction: 3-SAT

\le_p

INDEPENDENT-SET

Given: the 3-CNF formula $\varphi = (x_1 \vee \bar{x}_2 \vee x_3) \wedge (\bar{x}_1 \vee x_2 \vee x_3)$ , with 2 clauses ( $m=2$ ).

Construction (the reduction $f$ ):

Step 1: For each clause, make a triangle of 3 vertices, one per literal. Two triangles → 6 vertices.
Step 2: Add edges within each triangle (so at most one literal per clause is chosen).
Step 3: Add edges between any two vertices labeled by complementary literals (e.g. $x_1$ in clause 1 connects to $\bar{x}_1$ in clause 2).
Step 4: Set the target independent-set size $k = m = 2$ .

Claim: $\varphi$ is satisfiable $\iff$ the graph has an independent set of size $k=2$ .

Verification of equivalence: picking $x_1 = \text{T}, x_2=\text{T}, x_3=\text{anything}$ satisfies both clauses. Choose vertex $x_1$ from clause 1 and vertex $x_2$ from clause 2: not adjacent (different triangles, not complementary), so they form an independent set of size 2. ✓

Cost of $f$ : $O(m)$ vertices and $O(m^2)$ edges, built in polynomial time.

\boxed{f(\varphi) = (G, k=2);\ \ \varphi \text{ SAT} \iff G \text{ has independent set of size } 2.}

This shows INDEPENDENT-SET is NP-hard (since 3-SAT is NP-complete), and as it is also in NP, it is NP-complete.

⚠️ Common mistake

"NP means non-polynomial." False. NP stands for nondeterministic polynomial time. Every problem in P is also in NP ( $\mathrm{P} \subseteq \mathrm{NP}$ ), because a P-algorithm verifies trivially by ignoring the certificate. Problems in NP have polynomial-size, polynomial-time-checkable certificates.

"NP-complete = unsolvable." False. NP-complete problems are decidable; we have algorithms (e.g. exhaustive search in $\sim 2^n$ time). They are merely believed not to have polynomial-time algorithms.

"If P ≠ NP, then no NP-complete instance can be solved fast." False. P vs NP is about worst-case asymptotic behavior. Modern SAT solvers handle industrial instances with millions of variables. Hardness is about families that force exponential blowup, not every instance.

"Proving one NP-complete problem hard proves P ≠ NP." Backwards — you'd need to prove a lower bound that no polynomial algorithm exists, which is exactly the open problem.

Counterexample

Not every hard-looking problem is NP-complete. Consider PRIMES (is $n$ prime?). For decades it sat in NP and co-NP, suspected hard, and one might guess it NP-complete. But in 2002 Agrawal, Kayal, and Saxena gave the AKS algorithm, a deterministic polynomial-time test, placing PRIMES firmly in P. So a problem can look like a candidate for NP-completeness yet actually be efficiently solvable. Likewise 2-SAT (clauses of 2 literals) is in P via implication-graph SCC analysis, even though its cousin 3-SAT is NP-complete — a sharp jump in complexity from 2 to 3 literals per clause.

connection

Co-NP and the Polynomial Hierarchy: co-NP is the class of problems whose "no"-answers have short certificates (e.g. TAUTOLOGY). Whether NP = co-NP is open and would follow from P = NP. Iterating $\exists/\forall$ quantifiers builds the polynomial hierarchy PH, which collapses if P = NP.
Space Complexity and PSPACE: $\mathrm{NP} \subseteq \mathrm{PSPACE}$ ; quantified Boolean formulas (TQBF) are PSPACE-complete, generalizing SAT.
Approximation Algorithms: when exact solutions are NP-hard, we seek provably near-optimal answers; the PCP theorem governs which problems are hard to even approximate.
Randomized Algorithms and BPP: the class BPP of efficient randomized computation relates to P; many conjecture P = BPP.
Reductions and Completeness: the unifying machinery — completeness exists for many classes (P-complete, PSPACE-complete, #P-complete).

🔬 Where this appears

⏳ History

- 1936 — Alan Turing defines the Turing machine, fixing a rigorous notion of computability and the decidable/undecidable boundary.

- 1956 — Kurt Gödel, in a letter to von Neumann, essentially poses the P vs NP question, asking whether a certain theorem-proving search can avoid brute force — only rediscovered decades later.

- 1965 — Hartmanis and Stearns found computational complexity with the time-hierarchy framework; Cobham and Edmonds independently identify polynomial time as the formal notion of "efficient."

- 1971 — Stephen Cook proves SAT is NP-complete (STOC), launching the theory.

- 1972 — Richard Karp's landmark paper "Reducibility Among Combinatorial Problems" shows 21 classic problems (clique, vertex cover, Hamiltonian cycle, knapsack, etc.) are NP-complete, demonstrating the phenomenon's vast reach.

- 1973 — Leonid Levin's independent work on universal search problems is published in the USSR.

- 1979 — Garey and Johnson publish Computers and Intractability, the canonical catalog of NP-complete problems and the field's standard reference.

- 1992 — The PCP theorem (Arora, Safra; Arora, Lund, Motwani, Sudan, Szegedy) characterizes NP via probabilistically checkable proofs, revolutionizing hardness-of-approximation.

- 2000 — The Clay Mathematics Institute names P vs NP a Millennium Prize Problem with a US

1,000,000 reward; **2002** AKS proves PRIMES

\in$ P.

open-problem

Does P = NP? Unresolved. Most researchers believe P ≠ NP, but no proof exists either way. Key obstacles to a proof:

Relativization (Baker–Gill–Solovay, 1975): There exist oracles $A, B$ with $\mathrm{P}^A = \mathrm{NP}^A$ but $\mathrm{P}^B \ne \mathrm{NP}^B$ . So any proof technique that "relativizes" (works relative to all oracles) — like simple diagonalization — cannot settle P vs NP.
Natural Proofs (Razborov–Rudich, 1994): Broad classes of circuit lower-bound arguments, if successful against strong pseudorandom generators, would themselves break cryptography — a barrier suggesting current combinatorial methods are insufficient.
Algebrization (Aaronson–Wigderson, 2008): An extension of relativization showing algebraic techniques also fall short.

Ladner's theorem (1975): If P ≠ NP, there exist NP-intermediate problems — in NP, not in P, but not NP-complete. Candidates include graph isomorphism and factoring. So the world of NP is richer than a simple P / NP-complete dichotomy. Related open questions: Is NP = co-NP? Does the polynomial hierarchy collapse? Is graph isomorphism NP-complete (Babai's 2015 quasipolynomial algorithm suggests not)?

Figure

The conjectured landscape of complexity classes assuming P ≠ NP. NP-complete and NP-intermediate problems lie outside P.

Complexity Theory: P, NP, and NP-Completeness

Formal Statement

Building Intuition

Worked Examples

Common Misconceptions

Connections

Real-World Applications

Historical Development

Subtleties & Limits

See Also