Computational complexity: P and NP

SAT is clearly in NP: a satisfying assignment is a certificate that can be checked in polynomial time by simply plugging in the values. The deep part is showing every NP problem reduces to SAT — this works because a Boolean formula is expressive enough to describe, step by step, the entire run of any polynomial-time verifier, cell by cell and moment by moment, so "does a certificate exist" becomes "is this giant formula satisfiable".

Let $A \in NP$ with polynomial-time verifier $V$ running in time at most $n^k$ on inputs of length $n$ paired with a certificate of length at most $n^k$. Fix an input $x$ of length $n$; we build a Boolean formula $\phi_x$, satisfiable exactly when some certificate makes $V$ accept.

Imagine the entire computation of $V$ on $(x,y)$, for an unknown certificate $y$, laid out as a tableau: an $n^k \times n^k$ grid where row $t$ records the verifier's full tape contents and head position at time step $t$. Introduce a Boolean variable for every (cell, time-step, possible symbol) triple, recording what symbol sits in that cell at that time — since the grid has polynomially many cells and time steps, this is a polynomial number of variables.

The formula $\phi_x$ is built as a conjunction (AND) of clauses enforcing four local, easily-checkable conditions: (1) every cell holds exactly one symbol at each time step; (2) row $0$ correctly encodes the fixed input $x$ followed by a blank placeholder for the yet-to-be-guessed certificate $y$; (3) each small window of adjacent cells across two consecutive time steps is consistent with $V$'s transition rules (this is where the certificate bits, left free in row $0$, get to influence the rest of the computation); (4) some cell at the final time step records the accept state.

Each of these conditions only constrains a small, fixed-size neighborhood of variables, so each translates into a constant number of clauses, and there are only polynomially many neighborhoods to constrain — so $\phi_x$ has polynomial size and is computable from $x$ in polynomial time. By construction, $\phi_x$ is satisfiable exactly when there is a consistent tableau, i.e. exactly when some certificate $y$ makes $V(x,y)$ accept, i.e. exactly when $x \in A$. This exhibits the reduction $A \le_p \text{SAT}$ for an arbitrary $A \in NP$, and combined with $\text{SAT} \in NP$ shown above, proves SAT is NP-complete.

NP-completeness of $B$ means every NP problem can be rewritten, in polynomial time, as an instance of $B$. If $B$ itself can then be solved in polynomial time, chaining the rewriting step and the solving step together solves the original NP problem in polynomial time too — so a single tractable NP-complete problem drags every NP problem down into P with it.

Suppose $B$ is NP-complete and there is an algorithm solving $B$ in time $O(n^{k_1})$. Take any $A \in NP$; by NP-completeness of $B$, $A \le_p B$, meaning there is a reduction function $f$ computable in time $O(n^{k_2})$ that maps instances of $A$ to instances of $B$ while preserving yes/no answers.

On an input $x$ of length $n$ for $A$, first compute $f(x)$: this takes time $O(n^{k_2})$, and in particular the output $f(x)$ has length at most $O(n^{k_2})$ (a polynomial-time algorithm cannot write more output than time it runs). Then run the polynomial-time algorithm for $B$ on $f(x)$: since $|f(x)| = O(n^{k_2})$, this takes time $O\big((n^{k_2})^{k_1}\big) = O(n^{k_1 k_2})$.

The total running time is $O(n^{k_2}) + O(n^{k_1 k_2}) = O(n^{k_1 k_2})$, still a polynomial in $n$ (the composition of two polynomials is a polynomial). By the correctness of the reduction, $x$ is a yes-instance of $A$ if and only if $f(x)$ is a yes-instance of $B$, so this combined procedure correctly decides $A$ in polynomial time.

Since $A \in NP$ was arbitrary, every NP problem has a polynomial-time algorithm, i.e. $NP \subseteq P$. Combined with the always-true containment $P \subseteq NP$, this gives $P = NP$.