Polynomial-Time Reductions

A decision problem is a language $L \subseteq \{0,1\}^*$: a set of strings (encoding instances) that should be accepted. Given two decision problems $A$ and $B$, a Karp reduction (also called a many-one reduction, written $A \le_p B$) is a function $f : \{0,1\}^* \to \{0,1\}^*$ satisfying two conditions: 1. Efficiency: $f$ is computable by a deterministic algorithm running in time polynomial in $|x|$, the length of the input. 2. Correctness (the reduction property): for every string $x$,

The function $f$ takes an instance of $A$ and produces an instance of $B$ — not a solution, not a proof, just a translated instance whose membership status matches the original. This is the crucial subtlety: $f$ never needs to look at whether $x \in A$ actually holds; it only needs to construct an instance of $B$ that will turn out to be a yes-instance exactly when $x$ was a yes-instance of $A$. It helps to separate two distinct roles that reductions play, both essential vocabulary going forward. When we say "$A$ reduces to $B$," we mean $A \le_p B$: $A$'s difficulty is at most $B$'s difficulty, because a $B$-solver gives an $A$-solver. This is used to prove $B$ is hard, by reducing a known-hard problem into $B$. Confusing the direction of the arrow is the single most common error when learning this material — reducing $B$ into $A$ proves nothing about $A$'s hardness, it only shows $A$ is at least as hard as $B$, which is often useless if $B$ is easy. A problem $B$ is called NP-hard if every problem in NP reduces to it: $A \le_p B$ for all $A \in \mathrm{NP}$. A problem that is NP-hard and itself in NP is NP-complete. Proving NP-hardness of some new problem $B$ directly from the definition would require exhibiting a reduction from every problem in NP — an infinite family. The escape hatch, formalized by the Cook-Levin Theorem, is that it suffices to reduce just one already-known NP-hard problem $A$ into $B$, because $A \le_p B$ combined with (every problem in NP) $\le_p A$ gives, by transitivity, (every problem in NP) $\le_p B$.

Constructing a valid reduction $A \le_p B$ is a design task with a fixed recipe. You are given an arbitrary instance $x$ of $A$ (you do not get to assume anything about $x$ beyond that it is some valid encoding of an $A$-instance), and you must build, using only polynomial time and space, an instance $y = f(x)$ of $B$ such that the two yes/no answers agree.

Step-by-step recipe: 1. Understand both problems' input/output semantics precisely. What counts as a valid instance of $A$? Of $B$? What does "yes" mean for each? 2. Design the gadget. Identify how the combinatorial structure of $A$ (variables, constraints, graph edges, whatever the objects are) can be encoded using the vocabulary of $B$'s objects. This is the creative core of the proof. 3. Specify $f$ as an explicit polynomial-time algorithm. Write pseudocode that reads $x$ and outputs $y$. 4. Prove the forward direction: if $x \in A$, then $f(x) \in B$. Usually done by taking a witness/certificate for $x \in A$ and explicitly constructing a corresponding witness for $f(x) \in B$. 5. Prove the backward direction: if $f(x) \in B$, then $x \in A$. Usually done by taking a witness for $f(x) \in B$ and decoding it back into a witness for $x \in A$. This direction is the one most often shortchanged in sloppy proofs — it must be argued with equal rigor. 6. Verify the size and time bound. Confirm $|f(x)|$ is polynomial in $|x|$, and that steps 1–3 run in polynomial time (which, in particular, guarantees $|f(x)|$ is polynomial, since a polynomial-time algorithm cannot write more than a polynomial number of output symbols). Here is this recipe expressed generically, followed by the concrete, fully worked reduction 3-SAT $\le_p$ Independent Set that is used throughout the rest of the article. ``` FUNCTION Reduce_A_to_B(x): // x is an instance of A // 1. Parse x according to A's format parsed <- Parse(x) // 2. Build gadgets that encode parsed's structure using B's vocabulary y <- BuildInstanceOfB(parsed) // must run in poly(|x|) time // and produce |y| = poly(|x|) RETURN y // y is an instance of B // Correctness obligation (proved separately, not executed): // x in A <=> Reduce_A_to_B(x) in B ```

Concrete instance: 3-SAT $\le_p$ Independent Set.

• 3-SAT instance ($A$): a Boolean formula $\varphi = C_1 \wedge C_2 \wedge \cdots \wedge C_m$ in conjunctive normal form, each clause $C_i$ a disjunction of exactly 3 literals. Question: is there a truth assignment satisfying every clause?
• Independent Set instance ($B$): a graph $G = (V,E)$ and an integer $k$. Question: is there a set $S \subseteq V$ with $|S| \ge k$ such that no two vertices in $S$ are joined by an edge?

The gadget. For each clause $C_i = (\ell_{i1} \vee \ell_{i2} \vee \ell_{i3})$, create a triangle of three vertices, one per literal occurrence, and connect all three with edges (so at most one vertex per triangle can be chosen in any independent set). Then, for every pair of vertices across different triangles that represent complementary literals (one is $x_j$, the other $\neg x_j$), add a conflict edge between them. Set $k = m$, the number of clauses. ``` FUNCTION ThreeSAT_to_IndependentSet(phi): V <- empty set, E <- empty set m <- number of clauses in phi FOR each clause C_i = (l_i1, l_i2, l_i3) in phi: create vertices v_i1, v_i2, v_i3 add v_i1, v_i2, v_i3 to V add edges (v_i1,v_i2), (v_i2,v_i3), (v_i1,v_i3) to E // triangle FOR each pair of vertices v_ip, v_jq (i != j): IF literal at v_ip is the negation of literal at v_jq: add edge (v_ip, v_jq) to E // conflict edge k <- m RETURN (G = (V,E), k) ``` This algorithm clearly runs in time $O(m^2)$ (at most $3m$ vertices, and all pairs are checked once), which is polynomial in $|\varphi|$.

Complexity of the reduction itself. The reduction must run in time polynomial in the size of the input instance $x$. This is not a minor technicality: if the translation itself took exponential time, an efficient algorithm for $B$ would not yield an efficient algorithm for $A$, since the translation step would dominate the running time. In the 3-SAT-to-Independent-Set example, with $m$ clauses the construction creates $O(m)$ vertices and checks $O(m^2)$ pairs for conflicts, giving $O(m^2)$ time — polynomial, as required. A polynomial-time bound also automatically forces $|f(x)|$ to be polynomially bounded, since an algorithm cannot output more symbols than time steps it takes.

Why hardness transfers — the composition argument. This is the theorem that makes the whole machinery worthwhile. > Claim. If $A \le_p B$ and $A$ is NP-hard, then $B$ is NP-hard. > > Proof. Since $A$ is NP-hard, for every problem $C \in \mathrm{NP}$ we have $C \le_p A$, via some polynomial-time reduction $g$. We are given a polynomial-time reduction $f$ witnessing $A \le_p B$. Define $h = f \circ g$, i.e. $h(x) = f(g(x))$. > > Polynomial time: $g$ runs in time $p(|x|)$ for some polynomial $p$, producing an output $g(x)$ of length at most $p(|x|)$. Then $f$ runs in time $q(|g(x)|) \le q(p(|x|))$ for some polynomial $q$. The composition $q(p(|x|))$ is again a polynomial in $|x|$ (a polynomial composed with a polynomial is a polynomial). So $h$ runs in polynomial time. > > Correctness: $x \in C \iff g(x) \in A$ (since $g$ witnesses $C \le_p A$), and $g(x) \in A \iff f(g(x)) \in B$ (since $f$ witnesses $A \le_p B$). Chaining these, $x \in C \iff h(x) \in B$. > > Hence $C \le_p B$ for every $C \in \mathrm{NP}$, so $B$ is NP-hard. $\blacksquare$ This proof is exactly why $\le_p$ is called transitive: $A \le_p B$ and $C \le_p A$ together give $C \le_p B$. In practice, to prove a new problem $B$ is NP-hard, you only ever need to exhibit one reduction from one already-established NP-hard problem $A$ — the transitivity handles the rest, because that established problem already carries reductions in from all of NP.

Correctness of an individual reduction. For the 3-SAT $\le_p$ Independent Set construction above, correctness requires proving both directions of the iff. ($\Rightarrow$) If $\varphi$ is satisfiable, then $G$ has an independent set of size $k=m$. Take a satisfying assignment. In each clause, at least one literal is true; pick one true literal per clause and select its corresponding vertex in that clause's triangle — this gives exactly $m$ vertices, one per triangle. No two selected vertices lie in the same triangle (so no triangle edge is violated), and no two selected vertices are complementary literals — because if both $x_j$ and $\neg x_j$ were selected, the assignment would have to make both true, which is impossible. So no conflict edge is violated either. This set of $m$ vertices is independent. ($\Leftarrow$) If $G$ has an independent set $S$ of size $\ge m$, then $\varphi$ is satisfiable. Since each triangle is a clique, $S$ contains at most one vertex per triangle; with $m$ triangles and $|S| \ge m$, $S$ must contain exactly one vertex from every triangle. Because $S$ is independent, it contains no conflict edge, meaning $S$ never simultaneously selects both $x_j$ and $\neg x_j$ for any variable $j$. Assign each variable mentioned in $S$ the truth value matching its selected literal; assign unmentioned variables arbitrarily. Every clause has its selected literal set true, so $\varphi$ is satisfied. Both directions are essential: the forward direction shows the translation doesn't lose solutions, and the backward direction shows it doesn't invent fake ones.

Tradeoffs and honesty about scope. A polynomial-time reduction says nothing about how much larger $B$'s hard instances get, nor about average-case difficulty — it is purely a worst-case, existence-of-instance statement. It also does not directly give an approximation-preserving guarantee: some reductions blow up the "quality" of near-solutions, which is why approximation-hardness needs stronger reduction notions (e.g., gap-preserving or L-reductions). Finally, $\le_p$ is not symmetric: $A \le_p B$ does not imply $B \le_p A$, and conflating the two directions is the most common conceptual error in this subject.

Trace the reduction on a concrete small formula, then verify both the constructed instance and the answer transfer correctly. Let

This is exactly the formula in the figure, with $m = 3$ clauses, so $k = 3$.

Now try the assignment $x_1 = \text{True}, x_2 = \text{True}, x_3 = \text{True}$. Check clauses: $C_1 = (T \vee T \vee F) = T$; $C_2 = (F \vee T \vee T) = T$; $C_3 = (T \vee F \vee T) = T$. All satisfied, so $\varphi \in \text{3-SAT}$. Following the forward-direction proof, pick one true literal per clause: from $C_1$ pick $x_1$ (vertex in $T_1$), from $C_2$ pick $x_2$ (vertex in $T_2$), from $C_3$ pick $x_3$ (vertex in $T_3$). Check this set $S = \{x_1^{(T_1)}, x_2^{(T_2)}, x_3^{(T_3)}\}$ is independent:

• No two lie in the same triangle. ✓
• Check conflict edges: is $x_1$–$\neg x_1$ present? We chose $x_1$ from $T_1$ and $x_2$ from $T_2$, not $\neg x_1$, so this edge does not touch $S$. Is $x_2$–$\neg x_2$ present? We chose $x_2$, not $\neg x_2$, so no conflict. Is $x_3$–$\neg x_3$ present between chosen vertices? We chose $x_3$ from $T_3$, and from $T_1$ we chose $x_1$ (not $\neg x_3$), so no conflict touches $S$. ✓

So $S$ is independent with $|S| = 3 = k$, confirming $G$ has the required independent set — exactly as the theorem guarantees. To see the backward direction concretely, suppose instead someone hands us the independent set $S' = \{x_1^{(T_1)}, \neg x_1^{(T_2)}, x_3^{(T_3)}\}$ as a candidate. This is not actually independent, because $x_1^{(T_1)}$ and $\neg x_1^{(T_2)}$ are joined by a conflict edge — illustrating exactly why the conflict-edge gadget is necessary: it is precisely what rules out inconsistent assignments from ever forming an independent set, keeping the two directions of the iff aligned.

Polynomial-time reductions are the load-bearing wall of computational complexity theory, but their influence reaches directly into engineering practice. When a systems engineer encounters a scheduling, routing, or resource-allocation problem and cannot find a fast algorithm, a reduction from a known NP-hard problem (often Boolean Satisfiability, Vertex Cover, or Traveling Salesman Problem) is the standard way to justify falling back on heuristics, approximation algorithms, or integer-programming solvers instead of searching for an exact polynomial algorithm. Compiler and hardware design use reductions to justify the use of SAT and SMT solvers for verification tasks: showing a verification question reduces from SAT (or to SAT, for solving) tells engineers exactly which off-the-shelf solver technology is appropriate. Cryptographic hardness assumptions are themselves built from reduction arguments — a cryptosystem's security proof is typically a reduction showing that breaking the scheme would let you solve a problem believed to be hard (e.g., factoring or discrete log). Modern fine-grained complexity extends the same idea to distinguish, say, $O(n^2)$ from $O(n^{2-\epsilon})$ time using reductions from conjectured-hard problems like 3SUM or the Strong Exponential Time Hypothesis, showing the reduction paradigm scales down from "polynomial vs. exponential" to much finer time-complexity questions. All of this rests on the same definitional core introduced here, and sets up the formal statement and proof of the Cook-Levin Theorem as well as the standard reduction web among NP-complete problems.

Ask the tutor: Can you walk me through why the backward direction of a reduction proof is often the harder one to get right, using a reduction other than 3-SAT to Independent Set?