Complexity Theory

Complexity theory classifies problems by how much time or space they require to solve. The key insight is that even among decidable problems, some are tractable (solvable efficiently, class P) and some are intractable (no known efficient solution, class NP). The boundary between these classes is the deepest open question in computer science.

P vs NP intuition: P contains problems solvable in polynomial time (e.g., sorting, shortest paths). NP contains problems whose solutions can be verified in polynomial time (e.g., SAT, travelling salesman). The question is whether being able to verify quickly implies being able to solve quickly. Almost everyone believes P ≠ NP, but no one has proven it.

NP-completeness intuition: NP-complete problems are the hardest problems in NP. If any NP-complete problem has a polynomial-time algorithm, then P = NP (and every problem in NP becomes efficiently solvable). The Cook-Levin theorem proved SAT is NP-complete by directly encoding a TM’s computation as a Boolean formula. Other NP-complete problems are proved by reducing from known NP-complete problems.

The running time of a deterministic TM $M$ on input $w$ is the number of steps $M$ takes before Halting. If $M$ never halts, the running time is $\infty$.

$M$ runs in time $t(n)$ if for every input $w$ of length $n$, $M$ halts within $t(n)$ steps.

Theorem 6.1. Let $t(n)$ be a function with $t(n) \geq n$. Every TM that runs in time $t(n)$ has An equivalent single-tape TM that runs in time $O(t^2(n))$.

Proof. A $k$-tape TM running in time $t(n)$ uses at most $t(n)$ tape cells on each tape. Simulating One step of the $k$-tape machine requires scanning the single-tape simulation from left to right To read all $k$ heads, then left to right again to update them. This costs $O(t(n))$ per simulated Step. Over $t(n)$ steps, the total is $O(t(n)^2)$. $\blacksquare$

Theorem 6.1a (Time Hierarchy Theorem). If $t_1, t_2$ are time-constructible functions with $t_1(n) \log t_1(n) = o(t_2(n))$ Then $\mathrm{TIME(t_1(n)) \subsetneq \mathrm{TIME(t_2(n))}}$.

Proof (idea). Use diagonalisation. Construct a TM $D$ that on input $x$ of length $n$:

1. Compute $t_2(n)$ (possible since $t_2$ is time-constructible).
2. Simulate all TMs $M_1, M_2, \ldots$ in parallel for $t_1(n)$ steps on input $x$.
3. If any $M_i$ accepts $x$ within $t_1(n)$ steps, $D$ does the opposite (reject).
4. Otherwise, accept.

$D$ runs in time $O(t_2(n))$ and differs from every TM that runs in time $O(t_1(n))$ on at least One input. $\blacksquare$

Corollary. $\mathrm{P \subsetneq \mathrm{EXPTIME}}$.

Definition. $\mathrm{TIME(t(n))} = \{L : L \mathrm{ is decided by a deterministic TM in O(t(n))\}}$.

Definition. $\mathrm{NTIME(t(n))} = \{L : L \mathrm{ is decided by a nondeterministic TM in O(t(n))\}}$.

$$\mathrm{P} = \bigcup_{k \geq 1} \mathrm{TIME}(n^k)$$

$\mathrm{P}$ is the class of languages decidable in polynomial time by a deterministic TM. This Captures the notion of “efficiently solvable.”

Examples of problems in P:

• Path connectivity (BFS/DFS): $O(V + E)$.
• Shortest paths (Dijkstra): $O((V + E) \log V)$.
• Sorting: $O(n \log n)$.
• 2-SAT: $O(n + m)$.
• Primality testing: $O(\log^6 n)$ (AKS algorithm).

$$\mathrm{NP} = \bigcup_{k \geq 1} \mathrm{NTIME}(n^k)$$

Equivalent definition. A language $L$ is in NP if there exists a polynomial-time verifier $V$ And a polynomial $p$ such that:

$$L = \{w : \exists c \mathrm{ with} |c| \leq p(|w|) \mathrm{ and} V(w, c) = \mathrm{accept}\}$$

The string $c$ is called a certificate (or witness).

Examples of problems in NP:

• SAT: certificate is a satisfying assignment.
• Clique: certificate is the set of vertices forming the clique.
• Travelling Salesman (decision): certificate is the tour.
• Subset Sum: certificate is the subset.
• Graph 3-Colouring: certificate is the colouring.
• Integer factorisation (decision version): certificate is a factor.

Theorem 6.2. $\mathrm{P \subseteq \mathrm{NP}}$.

Proof. Every deterministic polynomial-time algorithm is a special case of a nondeterministic one (with exactly one choice at each step). Alternatively, the certificate can be empty. $\blacksquare$

Theorem 6.2a. If $A \leq_p B$ and $B \in \mathrm{NP}$ Then $A \in \mathrm{NP}$.

Proof. Let $V_B$ be the polynomial-time verifier for $B$ and $f$ be the polynomial-time reduction. Then $V_A(w, c) = V_B(f(w), c)$ is a polynomial-time verifier for $A$. $\blacksquare$

Open question: $\mathrm{P} = \mathrm{NP}$? This is the most important open problem in computer Science. Most researchers believe $\mathrm{P \neq \mathrm{NP}}$.

Consequences of P = NP. If $\mathrm{P} = \mathrm{NP}$ Then every problem in NP (including SAT, Travelling Salesman, graph colouring, protein folding, etc.) would have polynomial-time algorithms. This would revolutionise optimisation, cryptography (RSA and most public-key systems would be broken), And artificial intelligence. However, after decades of research, no polynomial-time algorithm has Been found for any NP-complete problem, providing strong empirical evidence for $\mathrm{P \neq \mathrm{NP}}$.

A language $B$ is NP-complete if:

1. $B \in \mathrm{NP}$ And
2. $A \leq_p B$ for every $A \in \mathrm{NP}$ (polynomial-time mapping reduction).

A language is NP-hard if condition (2) holds (it need not be in NP).

Theorem 6.3 (Cook-Levin, 1971). $\mathrm{SAT}$ is NP-complete.

Proof (detailed sketch).

1. $\mathrm{SAT \in \mathrm{NP}}$: a satisfying assignment is a polynomial-size certificate that can be verified in polynomial time.

2. For any $L \in \mathrm{NP}$ There is a polynomial-time NTM $N$ that decides $L$ in time $n^k$ for some $k$. Given input $w$ of length $n$ Construct a Boolean formula $\phi_{N,w}$ that is satisfiable iff $N$ accepts $w$.

The formula encodes the tableau of $N$ on $w$: a table of size $n^k \times n^k$ where each cell $T[i, j]$ records the symbol at tape cell $j$ after step $i$ of the computation.

Variables: For each position $(i, j)$ in the tableau and each symbol $s$ in the combined state-tape alphabet $\Gamma" = Q \times \Gamma$ A variable $x_{i,j,s}$ indicating that cell $(i, j)$ contains $s$.

Constraints:

• Well-formedness: Each cell contains exactly one symbol. For each $(i, j)$: exactly one of \{x_{i,j,s} : s \in \Gamma} is true.
• Start configuration: Row 0 encodes $q_0$ at position 0, $w_1$ at position 1, etc.
• Transition correctness: For every $2 \times 3$ window of the tableau, the bottom row must be a valid successor of the top row according to $N$‘s transition function.
• Acceptance: Some cell in the last row contains $q_{\mathrm{accept}}$.

Each constraint can be expressed as a polynomial-size CNF formula (using standard encodings of “exactly one” and “window” constraints). The total formula has size $O(n^{2k})$ Which is polynomial in $|w|$. $\blacksquare$

Worked Example: Cook-Levin tableau construction (simplified)

Consider an NTM $N$ that decides a language $L$ in time $n^2$. On input $w = 01$ (length $n = 2$), The tableau is a $4 \times 4$ grid (since $n^2 = 4$).

The formula $\phi_{N,w}$ has variables for each cell. For instance, $x_{0,0,q_0}$ indicates That position $(0,0)$ contains the start state. The constraints enforce:

• Row 0: $q_0$ at position 0, 0 at position 1, 1 at position 2, $\sqcup$ at position 3.
• Transition windows: each $2 \times 3$ block must be consistent with $\delta$.
• Row 3: at least one cell contains $q_{\mathrm{accept}}$.

If $N$ accepts $w$ Then the accepting computation path provides a satisfying assignment (the tableau records that path). If $\phi_{N,w}$ is satisfiable, the satisfying assignment Encodes a valid accepting computation.

Corollary 6.4. If any NP-complete problem is in P, then P = NP.

Theorem 6.5. If $A \leq_p B$ and $B \in \mathrm{P}$ Then $A \in \mathrm{P}$.

Proof. To decide $A$ on input $w$: compute $f(w)$ in polynomial time (the reduction), then decide $B$ on $f(w)$ in polynomial time. Total: polynomial time. $\blacksquare$

3-SAT. Given a CNF formula with exactly 3 literals per clause, is it satisfiable?

Reduction: SAT $\leq_p$ 3-SAT. Replace each clause with more or fewer than 3 literals by Equivalent clauses with exactly 3 literals using auxiliary variables.

Theorem 6.5a. SAT $\leq_p$ 3-SAT.

Proof. Given a CNF formula $\phi$ Convert each clause to exactly 3 literals:

• Clause $(l_1)$ (1 literal): replace with $(l_1 \lor a \lor b) \land (l_1 \lor a \lor \bar{b}) \land (l_1 \lor \bar{a} \lor b) \land (l_1 \lor \bar{a} \lor \bar{b})$ where $a, b$ are new variables. This is satisfiable iff $l_1$ is true.
• Clause $(l_1 \lor l_2)$ (2 literals): replace with $(l_1 \lor l_2 \lor a) \land (l_1 \lor l_2 \lor \bar{a})$ where $a$ is new. Satisfiable iff $l_1 \lor l_2$ is true.
• Clause $(l_1 \lor l_2 \lor l_3)$: leave as is.
• Clause $(l_1 \lor \cdots \lor l_k)$ for $k \gt 3$: replace with $(l_1 \lor l_2 \lor z_1) \land (\bar{z}_1 \lor l_3 \lor z_2) \land \cdots \land (\bar{z}_{k-4} \lor l_{k-1} \lor l_k)$ where $z_i$ are new variables. Satisfiable iff the original clause is satisfiable.

Each transformation is polynomial-size and preserves satisfiability. $\blacksquare$

Vertex Cover. Given a graph $G = (V, E)$ and integer $k$ Is there a vertex cover of size $\leq k$?

Theorem 6.5b. 3-SAT $\leq_p$ Vertex Cover.

Proof (sketch). Given a 3-CNF formula $\phi$ with $k$ clauses and $n$ variables, construct a graph $G$:

1. For each variable $x_i$ Create a variable gadget: two vertices $x_i$ and $\bar{x}_i$ connected by an edge. Selecting $x_i$ into the cover corresponds to setting $x_i$ to true (removing $\bar{x}_i$ from consideration).
2. For each clause $C_j = (l_a \lor l_b \lor l_c)$ Create a clause gadget: a triangle of three vertices connected to the corresponding literal vertices in the variable gadgets.
3. Set the target: $k' = n + 2k$.

The cover must include at least one endpoint of each variable-gadget edge ($n$ vertices) and at least two vertices from each clause triangle ($2k$ vertices). Selecting a literal vertex in the Cover removes it from clause consideration; the remaining two triangle vertices must be in the Cover. The formula is satisfiable iff we can choose literal vertices such that each clause triangle has at most one vertex already excluded. $\blacksquare$

Clique. Given $G = (V, E)$ and integer $k$ Does $G$ contain a clique of size $k$?

Reduction: Vertex Cover $\leq_p$ Clique. $G = (V, E)$ has a vertex cover of size $k$ iff $\overline{G} = (V, \overline{E})$ has a clique of size $|V| - k$.

Proof. If $C \subseteq V$ is a vertex cover of size $k$ in $G$ Then every edge of $G$ has at Least one endpoint in $C$. So $V \setminus C$ is an independent set in $G$ Meaning every pair in $V \setminus C$ is an edge in $\overline{G}$. Hence $\overline{G}$ has a clique of size $|V| - k$. The converse is analogous. $\blacksquare$

Hamiltonian Path. Given a graph $G = (V, E)$ Does $G$ have a path visiting every vertex exactly Once?

Theorem 6.5c. Vertex Cover $\leq_p$ Hamiltonian Path (via Hamiltonian Cycle).

Proof (sketch). Given $(G, k)$ for Vertex Cover, construct a graph $G'$ such that $G$ has a Vertex cover of size $k$ iff $G'$ has a Hamiltonian cycle. The construction uses selection gadgets That choose $k$ vertices (the cover), verification gadgets that check every edge is covered, and Connecting gadgets that string the selections together into a single cycle. The construction is Polynomial. $\blacksquare$

Subset Sum. Given integers $S = \{s_1, \ldots, s_n\}$ and target $T$ Is there a subset summing To $T$?

Theorem 6.5d. 3-SAT $\leq_p$ Subset Sum.

Proof (sketch). Given a 3-CNF formula with variables $x_1, \ldots, x_n$ and clauses $C_1, \ldots, C_k$ Construct a set of numbers $S$ and target $T$ in decimal.

For each variable $x_i$ Create two numbers $v_i$ and $\bar{v}_i$. In the “variable digits” (first $n$ columns), $v_i$ has a 1 in column $i$ and 0 elsewhere; $\bar{v}_i$ also has a 1 in column $i$ and 0 elsewhere. This forces choosing exactly one of $v_i, \bar{v}_i$.

For each clause $C_j$ Add a “clause digit” (column $n + j$): in $v_i$ (resp. $\bar{v}_i$), This digit is 1 iff $x_i$ (resp. $\bar{x}_i$) appears in $C_j$. The target $T$ has 1 in Every digit. Choosing $v_i$ or $\bar{v}_i$ contributes to satisfying the clauses that contain That literal. $\blacksquare$

Partition. Given integers $S = \{s_1, \ldots, s_n\}$ Can $S$ be partitioned into two subsets of Equal sum?

Reduction chain:

$$\mathrm{SAT} \to \mathrm{3}\mathrm{-SAT} \to \mathrm{VertexCover} \to \mathrm{Clique}$$ $$\mathrm{SAT} \to \mathrm{3}\mathrm{-SAT} \to \mathrm{HamiltonianPath}$$ $$\mathrm{SAT} \to \mathrm{3}\mathrm{-SAT} \to \mathrm{SubsetSum} \to \mathrm{Partition}$$ $$\mathrm{SAT} \to \mathrm{3}\mathrm{-SAT} \to \mathrm{SubsetSum} \to \mathrm{Partition}$$

Worked Example: Reducing 3-SAT to Independent Set

Given a 3-CNF formula $\phi$ with $k$ clauses, construct a graph $G$:

1. For each clause $C_j$ Create a group of 3 vertices (one per literal).
2. Within each group, add all three edges (forming a triangle). At most one vertex per group can be in an independent set.
3. For each pair of contradictory literals ($x_i$ and $\bar{x}_i$) in different groups, add an edge. They cannot both be selected.

Set the target to $k$ (one vertex per clause). An independent set of size $k$ exists iff $\phi$ Is satisfiable: selecting one literal per clause without contradiction gives a consistent Satisfying assignment. $\blacksquare$

Definition. $\mathrm{SPACE(s(n))}$ is the class of languages decidable by a deterministic TM Using $O(s(n))$ tape cells. $\mathrm{NSPACE(s(n))}$ is the nondeterministic analogue.

Key classes:

• $\mathrm{L} = \mathrm{SPACE(\log n)}$, logarithmic space.
• $\mathrm{NL} = \mathrm{NSPACE(\log n)}$, nondeterministic logarithmic space.
• $\mathrm{PSPACE} = \bigcup_{k \geq 1} \mathrm{SPACE(n^k)}$.

Theorem 6.6 (Savitch, 1970). $\mathrm{NSPACE(s(n)) \subseteq \mathrm{SPACE(s(n)^2)}}$ For $s(n) \geq \log n$.

Proof (sketch). To decide whether an NTM using space $s(n)$ accepts, we check reachability in the Configuration graph. The graph has at most $N = |\Gamma|^{s(n)} \cdot s(n) \cdot |Q|$ nodes, where $|\Gamma|$ is the tape alphabet size and $|Q|$ the number of states. A deterministic TM can decide Reachability using the recursive algorithm $\mathrm{REACH(u, v, d)}$ (can $u$ reach $v$ in at most $d$ steps?), which uses $O(\log N) = O(s(n))$ space and recurses to depth $O(\log N)$. Total space: $O(s(n) \cdot \log N) = O(s(n)^2)$. $\blacksquare$

Corollary 6.7. $\mathrm{PSPACE} = \mathrm{NPSPACE}$.

Proof. $\mathrm{NPSPACE \subseteq \bigcup_k \mathrm{NSPACE(n^k) \subseteq \bigcup_k \mathrm{SPACE(n^{2k})}}} = \mathrm{PSPACE}$ by Savitch’s theorem. $\blacksquare$

NL-completeness. A language $B$ is NL-complete if $B \in \mathrm{NL}$ and every $A \in \mathrm{NL}$ is log-space reducible to $B$.

Theorem 6.8 (Immerman—Szelepcsényi, 1987). $\mathrm{NL} = \mathrm{coNL}$.

This is surprising because it is not known whether $\mathrm{NP} = \mathrm{coNP}$. The …/1-number-and-algebra/3_proof-and-logic uses An inductive counting argument: given an NTM for $L$ Construct an NTM for $\overline{L}$ that Counts the number of reachable configurations.

PSPACE-completeness. A language is PSPACE-complete if it is in PSPACE and every PSPACE problem Reduces to it. Key PSPACE-complete problems:

• TQBF (True Quantified Boolean Formula): Given a fully quantified Boolean formula $\phi = Q_1 x_1 Q_2 x_2 \cdots Q_n x_n \, \psi(x_1, \ldots, x_n)$ where $Q_i \in \{\forall, \exists\}$ and $\psi$ is a CNF formula, is $\phi$ true?

Theorem 6.9. TQBF is PSPACE-complete.

Proof (membership). Evaluate the quantifiers recursively. For $\exists x_i \phi$ Try both values Of $x_i$ and recurse. For $\forall x_i \phi$ Similarly. At depth $n$ Evaluate $\psi$. Each level Uses $O(n)$ space to store the current assignment, giving $O(n^2)$ total.

Proof (hardness). Reduce from any $L \in \mathrm{PSPACE}$ using the configuration graph. A Computation of a PSPACE TM on input $w$ of length $n$ uses at most $p(n)$ cells for some Polynomial $p$. The number of distinct configurations is at most $N = |\Gamma|^{p(n)} \cdot p(n) \cdot |Q|$ which is exponential. The statement ”$M$ accepts $w$” can be expressed as: “there exists a Configuration $c_1$ reachable from the start configuration in $\leq N$ steps such that for all Configurations $c_2$ reachable from $c_1$ in one step, there exists a configuration $c_3$…” This alternating reachability formula can be encoded as a quantified Boolean formula of Polynomial size. $\blacksquare$

Worked Example: Evaluating a QBF formula

Evaluate $\phi = \forall x \exists y \, [(x \lor y) \land (\bar{x} \lor y)]$.

• For $x = 0$: need $\exists y$ such that $(0 \lor y) \land (1 \lor y) = y \land \mathrm{true} = y$. So we need $y = 1$ (which exists).
• For $x = 1$: need $\exists y$ such that $(1 \lor y) \land (0 \lor y) = \mathrm{true \land y} = y$. So we need $y = 1$ (which exists).

Since both values of $x$ lead to a satisfying assignment for $y$, $\phi$ is true.

The polynomial hierarchy (PH) generalises the notions of NP and coNP through alternating Quantifiers.

Definition. Define the classes $\Sigma_k^P$ and $\Pi_k^P$ inductively:

• $\Sigma_0^P = \Pi_0^P = \mathrm{P}$.
• $\Sigma_{k+1}^P = \mathrm{NP}^{\Sigma_k^P}$ (NP with a $\Sigma_k^P$ oracle).
• ${\Pi_{k+1}^P} = \mathrm{coNP}^{\Sigma_k^P}$ (coNP with a $\Sigma_k^P$ oracle).
• $\mathrm{PH} = \bigcup_{k \geq 0} \Sigma_k^P$.

Equivalent characterisation. A language $L$ is in $\Sigma_k^P$ iff there exist polynomial-time Computable relations $R$ and polynomials $p$ such that:

$$L = \{x : \exists y_1 \forall y_2 \exists y_3 \cdots Q_k y_k \, R(x, y_1, \ldots, y_k)\}$$

Where each $|y_i| \leq p(|x|)$ and the quantifiers alternate, starting with $\exists$.

Examples:

• $\Sigma_1^P = \mathrm{NP}$: “there exists a certificate.”
• $\Pi_1^P = \mathrm{coNP}$: “for all certificates.”
• $\Sigma_2^P$ contains problems like “does there exist a strategy for player 1 such that for all strategies of player 2, player 1 wins?” (for polynomial-size games).
• $\Pi_2^P$ contains the complement of such problems.

Relationships:

$$\mathrm{P \subseteq \mathrm{NP \subseteq \Sigma_2^P \subseteq \Sigma_3^P \subseteq \cdots \subseteq \mathrm{PH \subseteq \mathrm{PSPACE }}}}$$

Theorem 6.10. If $\Sigma_k^P = \Sigma_{k+1}^P$ for some $k$ Then $\mathrm{PH} = \Sigma_k^P$ (the polynomial hierarchy collapses to level $k$).

Proof. If $\Sigma_k^P = \Sigma_{k+1}^P = \mathrm{NP}^{\Sigma_k^P}$ Then the $\Sigma_k^P$ oracle Provides no additional power. By induction, $\Sigma_{k+i}^P = \Sigma_k^P$ for all $i \geq 0$ So $\mathrm{PH} = \Sigma_k^P$. $\blacksquare$

It is widely believed that $\mathrm{PH}$ does not collapse.

coNP. The class of languages whose complements are in NP. A problem is in coNP if every “no” Instance has a polynomial-time verifiable certificate.

• Example: “Is this formula a tautology?” (the certificate for “no” would be a failing assignment).
• $\mathrm{P} \subseteq \mathrm{NP} \cap \mathrm{coNP}$.
• It is unknown whether $\mathrm{NP} = \mathrm{coNP}$. If $\mathrm{P} = \mathrm{NP}$ Then $\mathrm{NP} = \mathrm{coNP}$.

Theorem 6.11. If $\mathrm{NP} \neq \mathrm{coNP}$ Then $\mathrm{P} \neq \mathrm{NP}$.

Proof. If $\mathrm{P} = \mathrm{NP}$ Then $\mathrm{P} = \mathrm{coNP}$ (since $\mathrm{P}$ Is closed under complement), so $\mathrm{NP} = \mathrm{coNP}$. The contrapositive gives the Result. $\blacksquare$

PSPACE. The class of languages decidable in polynomial space:

$$\mathrm{PSPACE} = \bigcup_{k \geq 1} \mathrm{SPACE(n^k) }$$

• $\mathrm{P} \subseteq \mathrm{NP} \subseteq \mathrm{PSPACE}$.
• $\mathrm{P} \neq \mathrm{PSPACE}$ (space hierarchy theorem).
• PSPACE-complete problems: TQBF, generalised geography, determining the winner of a position in certain games.

EXPTIME. The class of languages decidable in exponential time:

$$\mathrm{EXPTIME} = \bigcup_{k \geq 1} \mathrm{TIME(2^{n^k}) }$$

• $\mathrm{P} \subseteq \mathrm{NP} \subseteq \mathrm{PSPACE} \subseteq \mathrm{EXPTIME}$.
• $\mathrm{P} \neq \mathrm{EXPTIME}$ (time hierarchy theorem).
• EXPTIME-complete problems: Generalised chess, Go (on sufficiently large boards), determining the winner of a two-player game with exponential game tree.

Hierarchy summary:

$$\mathrm{Regular \subsetneq \mathrm{CFL \subsetneq \mathrm{Decidable \subsetneq \mathrm{TM\mathrm{-recognisable} }}}}$$ $$\mathrm{L \subseteq \mathrm{NL \subseteq \mathrm{P \subseteq \mathrm{NP \subseteq \mathrm{PSPACE \subseteq \mathrm{EXPTIME }}}}}}$$ $$\mathrm{P \subseteq \mathrm{NP \subseteq \mathrm{PH \subseteq \mathrm{PSPACE }}}}$$

Both inclusions $\mathrm{P} \subseteq \mathrm{NP}$ and $\mathrm{NP} \subseteq \mathrm{PSPACE}$ are Known to be proper ($\mathrm{P} \neq \mathrm{PSPACE}$), but the status of $\mathrm{P}$ vs. $\mathrm{NP}$ remains open.

If P ≠ NP, are there languages between them; in NP but neither in P nor NP-complete? Or does every problem in NP sit at one extreme? Ladner’s theorem answers: there are NP-intermediate problems, and they can be constructed explicitly.

Theorem 6.12 (Ladner, 1975). If P ≠ NP, then there exists a language $L \in \mathrm{NP} \setminus \mathrm{P}$ that is not NP-complete.

Proof idea. Construct $L$ by diagonalisation over the polynomial-time deciders. The construction “squashes” SAT: $L$ contains exactly the strings in SAT whose length is a perfect square; but with the length threshold adjusted so that $L$ is neither trivially easy nor NP-complete. The construction alternates between two modes:

• Mode 1 (make it easy): On inputs of length $\leq n$, decide $L$ with the $n$-th polynomial-time machine $M_n$. If $M_n$ decides $L$ correctly, $L \notin \mathrm{P}$ is falsified; so switch to Mode 2.
• Mode 2 (make it hard): Ensure $L$ differs from the $n$-th NP-complete language on some input, by padding SAT instances; so if $L$ were NP-complete, SAT would reduce to $L$, which the padding prevents; so switch back to Mode 1.

The alternation is self-limiting: each switch happens later than the last, so $L$ is neither in P (Mode 1 always fails eventually) nor NP-complete (Mode 2 always blocks the reduction). The formal proof requires the delay trick to ensure the diagonalisation doesn’t outpace the polynomial bounds. $\blacksquare$

Ladner’s theorem tells us that the P vs. NP question is maximally fine-grained: either P = NP, or there is a genuine hierarchy of intermediate difficulty. The natural candidates; integer factorisation, graph isomorphism; are believed to be NP-intermediate.

Definition. $\mathrm{BPP}$ (Bounded-error Probabilistic Polynomial time) is the class of languages decidable by a probabilistic polynomial-time TM that, on every input, gives the correct answer with probability $\geq 2/3$.

The constant $2/3$ is arbitrary; amplification (repeating the computation $k$ times and taking the majority) raises the success probability to $1 - 2^{-ck}$ for a constant $c$ by the Chernoff bound, at a multiplicative cost of $O(k)$ in running time.

Theorem 6.13 (Adleman, 1978). $\mathrm{BPP} \subseteq \mathrm{P/poly}$.

Proof. Let $L \in \mathrm{BPP}$. Amplify the machine to error $\leq 2^{-2n}$ by running it $O(n)$ times. For each input $x$ of length $n$, the machine uses $m(n)$ random bits. Call a random string $r \in \{0,1\}^{m(n)}$ bad if it causes a wrong answer on some input $x$ of length $n$. By the union bound, the number of bad strings is $\leq 2^n \cdot 2^{-2n} \cdot 2^{m(n)} = 2^{m(n) - n}$. So if $m(n) \geq n + 2$, the bad strings are at most a $2^{-2}$ fraction of $\{0,1\}^{m(n)}$; most strings are good. Fix a good $r^*$: the deterministic machine that runs the randomised machine with $r^*$ hardwired is correct on every input of length $n$. The circuit family hardwires $r^*$ for each length. $\blacksquare$

This means BPP machines can be derandomised at the cost of non-uniform advice; and if $\mathrm{P} = \mathrm{BPP}$ (widely believed), the randomisation was never doing real work.

Definition. An oracle $A$ is a set of strings queryable in one step by a Turing machine. $\mathrm{P}^A$ and $\mathrm{NP}^A$ are the classes definable with oracle access to $A$.

Theorem 6.14 (Baker—Gill—Solovay, 1975). There exists an oracle $A$ such that $\mathrm{P}^A = \mathrm{NP}^A$, and there exists an oracle $B$ such that $\mathrm{P}^B \neq \mathrm{NP}^B$.

Proof idea. For $A$: let $A = \mathrm{TQBF}$ (PSPACE-complete). Then $\mathrm{NP}^A \subseteq \mathrm{PSPACE} \subseteq \mathrm{P}^A$ (the oracle answers any PSPACE query). For $B$: define $B$ by diagonalisation over all polynomial-time oracle machines, ensuring the constructed oracle answers queries to separate $\mathrm{P}^B$ from $\mathrm{NP}^B$. $\blacksquare$

The Baker—Gill—Solovay theorem is a caution: the techniques available to complexity theorists (relativising arguments) cannot resolve P vs. NP, because those techniques would apply equally well in the oracle worlds where the answer goes both ways. This is why the resolution of P vs. NP requires non-relativising techniques; which the circuit-complexity approach (circuit lower bounds) and the algebraic approach (arithmetisation in IP = PSPACE) exemplify.

Suppose a proof of a statement is written down, but you are allowed to randomly inspect only a handful of its positions – a constant number of characters – and, from that glance alone, accept correct proofs always and reject bogus ones with high probability. For most proof systems this is impossible: skip one step of a long calculation and you might miss the error. The PCP theorem says that for NP statements, such proofs exist – after rewriting the proof into a special redundant form.

Theorem 6.13 (Feige–Goldwasser–Lund–Safra–Szegedy 1991; Arora–Safra 1992; Arora–Lund–Motwani–Sudan–Szegedy 1992).

$$\mathrm{NP = PCP(O(\log n),\ O(1))}$$

A language $L$ is in NP if and only if there is a verifier $V$ that, given an input $x$ of length $n$ and oracle access to a proof $\pi$:

1. flips $O(\log n)$ random coins (so at most $\mathrm{poly}(n)$ possible inspection patterns),
2. queries constant many positions of $\pi$,
3. accepts or rejects – with completeness ≥ $\tfrac{2}{3}$ when $x \in L$ (some proof makes $V$ accept with probability 1 in the standard formulation), and soundness ≤ $\tfrac{1}{3}$ when $x \notin L$ (every proof fools $V$ on at most a third of its random choices).

The proof $\pi$ may be exponentially long in $n$ – the verifier never reads it all; it only probes.

Why “rewritten” matters. A vanilla NP witness (a satisfying assignment) has no such robust property: changing one variable’s value can be detected only by checking a constraint that mentions it. The PCP construction encodes the witness into a locally testable object where every error contaminates a constant fraction of the proof, so any inconsistent assignment corrupts enough positions that a constant-sample check catches it. Building such encodings is the entire difficulty of the theorem.

The engine: gap amplification. Start from a constraint-satisfaction view of NP: SAT compiles to a system of constant-size constraints where a satisfying assignment satisfies all of them. The PCP construction repeatedly applies a transformation that:

• keeps satisfiable systems perfectly satisfiable, and
• drives unsatisfiable systems’ maximum satisfiable fraction down by a constant factor,

while increasing the proof size only polynomially. After $O(\log n)$ amplification rounds, an unsatisfiable instance has no assignment satisfying more than a constant fraction below 1 – and at that point a verifier can sample a single random constraint, check it with a constant number of proof probes, and get soundness $1 - \varepsilon$. That constant gap is what makes $O(1)$ queries possible.

Dinur’s proof (2006). The original proofs were long and algebraic. Irit Dinur’s combinatorial proof reformulates the amplification as a graph powering step on constraint graphs: expand the constraint graph so that violations spread, then reduce alphabet size with a local test – repeat $O(\log n)$ times. This version is short enough to teach and is the standard reference for a first encounter.

The consequence that reshaped a field: hardness of approximation. Because the PCP reduction preserves a gap, it maps optimisation problems to themselves with a gap: MAX-3SAT compiles so that satisfiable instances stay fully satisfiable while unsatisfiable ones have no assignment satisfying more than a $1 - \varepsilon$ fraction of clauses. Any polynomial-time algorithm guaranteeing better than $1 - \varepsilon$ would distinguish the two cases – solving NP-complete SAT exactly. This yields optimal inapproximability constants:

Before the PCP theorem these gaps had no explanation; after it, “the best known approximation ratio equals random assignment” stopped being an embarrassment and became a theorem’s fingerprint.

Connection to interactive proofs. The PCP theorem is the compiled form of the IP = PSPACE result: an interactive proof protocol between a verifier and a (possibly untrusted) prover can be converted, by committing the prover to answers via Merkle-tree-style cryptographic hashing, into a non-interactive oracle proof inspectable in constant queries. This lineage – interactive proofs → probabilistically checkable proofs → delegation of computation – is the foundation of modern proofs of proximity, SNARKs, and verifiable delegation in blockchain systems.

In one sentence. Every NP statement has proofs that certify themselves: if the claim is true, some proof survives arbitrary probing; if false, every proof is caught by a constant-size glance – and this impossible-sounding object is exactly what makes approximation hardness and modern verifiable computation possible.

• Computability; the undecidability results that motivate the complexity classes.
• Algorithm Analysis; the concrete algorithms whose running times populate the complexity classes.

• Turing Machines — Complexity classes are defined in terms of Turing machine resources, connecting computational models to complexity.

• Algorithm Analysis — Complexity theory classifies the computational difficulty of problems that algorithms attempt to solve.

• Regular Languages — The Chomsky hierarchy places regular languages at the simplest level of the complexity hierarchy.

• Discrete Mathematics

• Algorithm Implementation

1. Confusing NP-hard with NP-complete. NP-hard means “at least as hard as every problem in NP” (under polynomial-time reductions). NP-complete means NP-hard and in NP. The halting problem is NP-hard but not NP-complete because it is not in NP (it is not even decidable). A problem can be NP-hard without being verifiable in polynomial time.

2. Assuming “NP” means “Not Polynomial.” NP stands for Nondeterministic Polynomial time. A problem is in NP if a proposed solution can be verified in polynomial time by a deterministic TM, regardless of how long it takes to find the solution. This is about verifiability, not solvability.

3. Believing that polynomial reductions prove a problem is “hard” in an absolute sense. Polynomial-time reductions show relative difficulty within the polynomial hierarchy. A problem reduced from SAT is “hard” only in the sense that solving it would solve SAT. It says nothing about the problem’s difficulty for small input sizes or with respect to other resource bounds.

4. Confusing the classes P and NP. P ⊆ NP is known (a deterministic TM is a special case of a non-deterministic one). The open question is whether P = NP, whether every problem verifiable in polynomial time is also solvable in polynomial time. Most experts believe P ≠ NP, but this is unproven.

5. Assuming NP ⊆ coNP is false. It is unknown whether NP = coNP. If it were true, then every problem whose “no” instances are efficiently verifiable would also have “yes” instances efficiently verifiable. This is considered unlikely but remains open, and is considered a harder question than P vs. NP by some researchers.

• Context-Free Languages
• Decidability
• Introduction
• Problem Set