P, NP, and Reductions

Until now this course has been a catalog of triumphs: sorting in $O(n\log n)$, shortest paths in near-linear time, spanning trees almost for free. It is tempting to believe that every problem yields to a clever enough algorithm. It does not. There is a large, eminently practical family of problems (scheduling, routing, packing, constraint satisfaction) for which, after more than half a century of effort, nobody has found an algorithm that is fast on every instance, and for which we have strong reasons to suspect none exists.

The theory of intractability is how we make that suspicion precise. Its central insight, due to Cook, Levin, and Karp, is that thousands of these stubborn problems are really the same problem in disguise. Solve any one of them quickly and you solve them all; prove any one of them hard and you have proved them all hard. This lesson assembles the three ideas needed to state that claim: decision problems, the classes $\mathsf{P}$ and $\mathsf{NP}$, and reductions.

Decision problems

To classify difficulty cleanly we restrict attention to problems with a yes-or-no answer. A decision problem asks, of each input, a single question whose answer is yes or no.

This seems like a severe restriction; surely we usually want to find a shortest tour, not merely learn whether a short one exists. But the two are rarely far apart. The optimization problem find the cheapest tour has a decision twin: is there a tour of cost at most $k$? If we can answer the decision question quickly for every $k$, a binary search over $k$ pins down the optimal cost, and a little more work recovers the tour itself. Decision problems lose almost nothing and gain a clean theory, so they are the objects we classify.

A word on encoding and size. An input is a string of bits; the size of an instance is the length of that string. We always assume a reasonable encoding (integers in binary, graphs as adjacency lists) because an artificially bloated encoding (say, integers in unary) could make a slow algorithm look fast. With reasonable encodings fixed, polynomial in the input size is a stable, machine-independent notion.

The class P

Some decision problems have algorithms whose running time is bounded by a polynomial in the input size. These are the problems we regard as tractable.

Why polynomial, and not, say, $n^2$ or better? Because polynomials are closed under the operations we constantly perform: addition, multiplication, and especially composition. If a polynomial-time algorithm calls a polynomial-time subroutine a polynomial number of times, the whole thing is still polynomial. This closure is what makes $\mathsf{P}$ stable: it does not depend on the particular machine model, the programming language, or whether we count $n^2$ as fast. Everything we have called efficient so far (sorting, shortest paths, matching, linear programming) lives in $\mathsf{P}$. The class is our formal stand-in for feasible.¹

The class NP

Now consider a problem like Hamiltonian Cycle: given a graph $G$, is there a cycle that visits every vertex exactly once? We know of no polynomial-time algorithm to decide this. But notice an asymmetry. If a benevolent oracle hands us a cycle and claims it is Hamiltonian, we can check the claim in linear time: walk the cycle, confirm it visits each vertex once and uses real edges. Finding the cycle seems hard; verifying a proposed cycle is easy.

This is the defining feature of the class $\mathsf{NP}$: a problem is in $\mathsf{NP}$ if every yes-instance has a short proof, a certificate, that can be checked quickly.

The name $\mathsf{NP}$ stands for nondeterministic polynomial time: one can equivalently picture a machine that guesses the certificate $y$ and then verifies it. The verifier definition avoids speaking of magical guessing; it asks only that correct yes-answers come with checkable evidence.²

Three points deserve emphasis.

• The certificate must be short (polynomial length) and the check must be fast (polynomial time). For Hamiltonian Cycle the certificate is the cycle; for SAT (is a boolean formula satisfiable?) it is a satisfying assignment; for $\text{Subset-Sum}$ it is the subset that hits the target.
• The asymmetry between yes and no is real. $\mathsf{NP}$ guarantees a certificate only for yes-instances. The problem of certifying a no (there is no Hamiltonian cycle) need not be in $\mathsf{NP}$; that belongs to a companion class, $\mathsf{co}\text{-}\mathsf{NP}$.
• Every problem in $\mathsf{P}$ is in $\mathsf{NP}$. If we can solve a problem in polynomial time, we can ignore any offered certificate and just decide the answer directly; an empty certificate suffices. So $\mathsf{P}\subseteq \mathsf{NP}$.

Reductions: comparing difficulty

We want to say problem $B$ is at least as hard as problem $A$ without knowing how hard either one actually is. The device that makes this possible is a reduction: a way to convert any instance of $A$ into an instance of $B$ that has the same answer, so that an algorithm for $B$ becomes an algorithm for $A$.

Read $A{\le }_{P}B$ as $A$ is no harder than $B$.³ Picture this as a transform–solve–transform pipeline: take the input, transform it into an input for the other problem, hand that to a solver for $B$, then transform the solver's output back into an answer for $A$. The solver for $B$ is used as a black-box subroutine, and we never look inside it.

The dashed box is the punchline: a fast solver for $B$, wrapped in the fast transformers on either side, is a fast solver for $A$. For a decision problem the right-hand transformer is trivial (pass the yes/no answer through unchanged), and the pipeline collapses to the textbook definition above: apply $f$, ask the $B$-question, report the answer. For a search problem (the warm-up below) the right-hand transformer does real work, turning $B$'s witness back into a witness for $A$. Either way, the diagram encodes the two ways every reduction is used, which are mirror images of each other.

• Upper bound (good news flows forward). If $A{\le }_{P}B$ and $B\in \mathsf{P}$, then $A\in \mathsf{P}$. Tractability of the harder problem drags the easier one along: run $f$, then the fast solver for $B$; the composition of two polynomials is a polynomial.
• Lower bound (bad news flows backward). If $A{\le }_{P}B$ and $A$ is known to be hard, then $B$ is hard too. For if $B$ had a fast algorithm, the pipeline above would give $A$ one as well, a contradiction.

It is the second direction that powers the theory of intractability. To show a new problem $B$ is hard, we reduce a known-hard problem $A$ to it. The direction is a notorious source of error: we reduce from the hard problem to the new one. Getting the arrow backwards proves nothing.

Two structural facts make ${\le }_P$ behave like an ordering of difficulty.

• Reflexivity is trivial and, crucially, transitivity holds: if $A{\le }_{P}B$ and $B{\le }_{P}C$, then $A{\le }_{P}C$, since we just compose the two translators, and a polynomial of a polynomial is still a polynomial. Chains of reductions are the raw material of the next lesson's reduction web.

A warm-up reduction: matching reduces to flow

Reductions are not a tool reserved for hardness arguments; we have already been using them to design algorithms. The cleanest example, motivating the whole idea, is bipartite matching. We are given a set of tasks $t_1,\dots ,t_m$, a set of workers $w_1,\dots ,w_n$, and a compatibility table, where $A[i,j]$ is true when task $t_i$ can be done by worker $w_j$. A matching assigns tasks to workers so that no task and no worker is used twice; we want a matching of maximum cardinality. There is a slogan worth remembering here:

We do not write a matching algorithm from scratch. Instead we reduce $\text{Bipartite-Matching}$ to $\text{Max-Flow}$, a problem we already know how to solve, and reuse that solver. This is the pipeline of the previous section made concrete, and because matching is a search problem, the output transformer is no longer trivial.

Transform the input. Build a flow network: add a source $s$ and a sink $t$. Direct an edge $s\to t_i$ for every task, an edge $w_j\to t$ for every worker, and an edge $t_i\to w_j$ whenever $A[i,j]$ is true. Give every edge capacity $1$. The unit capacities out of $s$ and into $t$ are exactly the budget constraints: each task and each worker can carry at most one unit.

Solve with the black box. Run any max-flow algorithm (Ford–Fulkerson or Edmonds–Karp) and let $f^{\ast }$ be the maximum flow. The value $|f^{\ast }|$ is the size of the largest matching.

Transform the output. A flow value is just a number; the matching is recovered by reading off which compatibility edges $t_i\to w_j$ carry one unit of flow. Those edges are the assignment.

Two claims make the reduction correct, and it's worth separating them:

• Easy direction. If some $k$ tasks can be assigned, then pushing one unit along each chosen $s\to t_i\to w_j\to t$ path gives a flow of value $k$. So the max flow is at least as large as the best matching.
• Less easy direction. If the max flow value is $k$, then $k$ tasks can be assigned. This needs the integrality theorem: when every edge capacity is an integer, some maximum flow is integral (every $f_{uv}\in \mathbb{Z}$) and Ford–Fulkerson actually finds such a flow. With unit capacities, integral means each edge carries $0$ or $1$, and an integral flow decomposes into a collection of edge-disjoint $s$–$t$ path flows. Each path uses one task and one worker, so the paths are a matching of size $k$.

Both directions together give $|f^{\ast }|=$ (size of maximum matching), so the reduction is valid. The transform–solve–transform diagram now does real work: build the network ($f$), call the flow solver ($B$), decompose the integral flow into paths (the output transformer). We obtained a matching algorithm without writing one, purely because $\text{Bipartite-Matching}{\le }_P\text{Max-Flow}$.

A small reduction between decision problems

The matching reduction reused an easy solver to solve another easy problem. The reductions that drive intractability go the other way, relating two decision problems with no known fast solver, but the mechanism is identical. Here is a textbook example. $\text{Independent-Set}$ asks: given a graph $G$ and integer $k$, is there a set of $k$ vertices no two of which are adjacent? Clique asks: is there a set of $k$ vertices that are all pairwise adjacent? These are the same question asked of complementary graphs.

Given an instance $(G,k)$ of $\text{Independent-Set}$, build the complement graph $\bar{G}$ on the same vertices, where $uv$ is an edge of $\bar{G}$ exactly when it is not an edge of $G$. A set $S$ is independent in $G$ (no edges inside it) precisely when $S$ is a clique in $\bar{G}$ (all edges inside it). So $(G,k)\in \text{Independent-Set}\leftrightarrow (\bar{G},k)\in \text{Clique}.$ Constructing $\bar{G}$ takes time polynomial in the size of $G$, so this is a valid reduction $\text{Independent-Set}{\le }_P\text{Clique}$, and, since complementation is its own inverse, the reverse reduction holds too. The two problems are equivalent in difficulty: a fast algorithm for either yields one for the other.⁴

The P versus NP question

We now have two classes with $\mathsf{P}\subseteq \mathsf{NP}$. Problems in $\mathsf{P}$ can be solved quickly; problems in $\mathsf{NP}$ can at least have their solutions checked quickly. The defining open question of theoretical computer science is whether checking is genuinely easier than solving.

Almost everyone believes the answer is no: that $\mathsf{P}\ne \mathsf{NP}$, and that finding a needle is fundamentally harder than recognizing one once found. But no proof is known in either direction, and the question carries a million-dollar Clay Millennium Prize.⁵ What makes it more than a curiosity is the next lesson's discovery: there are problems in $\mathsf{NP}$, the $\mathsf{NP}$-complete problems, that are universally hardest. Every problem in $\mathsf{NP}$ reduces to each of them. A polynomial-time algorithm for even one would collapse $\mathsf{P}$ and $\mathsf{NP}$ into a single class; a proof that even one requires super-polynomial time would settle the question the other way.

The sketch shows the conjectured world: $\mathsf{P}$ and the $\mathsf{NP}$-complete problems sit as disjoint regions inside $\mathsf{NP}$. If $\mathsf{P}=\mathsf{NP}$, all three regions coincide and the entire picture collapses to a single blob. We do not know which world we live in, but we will see that the two regions, if separate, can never overlap.

Takeaways

• We study decision problems (yes/no answers); optimization problems reduce to them by binary search, so little is lost.
• $\mathsf{P}$ is the class of problems solvable in polynomial time; $\mathsf{NP}$ is the class of problems whose yes-answers admit a short, polynomial-time checkable certificate. Always $\mathsf{P}\subseteq \mathsf{NP}$.
• A polynomial-time reduction $A{\le }_{P}B$ is a transform–solve–transform pipeline: transform the input, call a black-box solver for $B$, transform its output back. It means $A$ is no harder than $B$: tractability flows forward ($B$ easy $\Rightarrow A$ easy), hardness flows backward ($A$ hard $\Rightarrow B$ hard). To prove $B$ hard, reduce a known hard problem to$B$.
• Reductions also build algorithms: $\text{Bipartite-Matching}{\le }_P\text{Max-Flow}$ solves matching by routing it through a flow solver, with the integrality theorem guaranteeing the flow decomposes back into a matching.
• Reductions compose, so ${\le }_P$ chains, building a web of equivalent difficulty.
• Whether $\mathsf{P}=\mathsf{NP}$, that is, whether checking is as easy as solving, is the central open question, and the hardest problems in $\mathsf{NP}$ hold the key.