Polynomial-Time Mapping Reductions

A mapping reduction (also called a many-to-one reduction, written $A \le_p B$) is a function $f$ that translates instances of a decision problem $A$ into instances of a decision problem $B$, such that membership is preserved exactly: $w \in A$ if and only if $f(w) \in B$. Formally, given languages $A \subseteq \Sigma^*$ and $B \subseteq \Sigma^*$, we say $A$ is polynomial-time mapping reducible to $B$ if there exists a function $f : \Sigma^* \to \Sigma^*$, computable by a deterministic Turing machine (or ordinary algorithm) running in time polynomial in $|w|$, satisfying

The word "mapping" emphasizes that $f$ is a total function applied once to the input — it is not an oracle call, not a subroutine invoked many times, and not allowed to inspect whether $f(w)$ is actually in $B$. This is the defining restriction that separates mapping reductions from more general (Turing) reductions, which may call a hypothetical solver for $B$ many times and combine the answers arbitrarily. The crucial asymmetry to internalize: $A \le_p B$ is a statement about the direction of difficulty comparison. It says $B$ is at least as expressive/hard as $A$, because any decision procedure for $B$ immediately yields one for $A$ (just apply $f$ first, then decide membership in $B$). It does not claim the reverse. Two consequences follow, and both are used constantly when reasoning about The Class P and The Class NP:

• If $A \le_p B$ and $B \in P$, then $A \in P$. (Easiness transfers backward along the reduction arrow.)
• If $A \le_p B$ and $A \notin P$ (assuming $A$ is known hard), then $B \notin P$ — provided $\mathrm{P} \ne \mathrm{NP}$ style separations, or more directly: $B$ cannot be easier than $A$ once you account for the polynomial overhead of computing $f$.

This second consequence, iterated across many problems, is exactly the technique used to prove a problem is NP-complete: reduce a known NP-complete problem into the new problem, showing the new problem inherits the hardness.

Constructing a mapping reduction is a design process, not a mechanical procedure — there is no single algorithm that produces reductions automatically (if there were, $\mathrm{P}$ vs $\mathrm{NP}$ would likely be settled). Instead, there is a disciplined recipe for building and verifying one.

Step 1 — Understand both languages precisely. Write out exactly what counts as a yes-instance of $A$ and of $B$. Sloppy definitions are the source of most incorrect reductions.

Step 2 — Design the gadget. Find a way to encode the combinatorial structure that makes an instance of $A$ a "yes" using the vocabulary of $B$. This is where creativity lives: e.g., encoding a Boolean formula's clauses as a graph's edges, or encoding a scheduling deadline as a numeric constraint.

Step 3 — Specify $f$ as an explicit algorithm. Write pseudocode that, given an instance $w$ of $A$, constructs an instance $f(w)$ of $B$, using only polynomially many steps and polynomially many symbols relative to $|w|$.

Step 4 — Prove the forward direction. Show: if $w \in A$, then $f(w) \in B$. Typically this means: take a witness/certificate that $w \in A$, and use it to explicitly construct a witness that $f(w) \in B$.

Step 5 — Prove the backward direction. Show: if $w \notin A$, then $f(w) \notin B$. Equivalently (and often easier to argue): if $f(w) \in B$, then $w \in A$ — i.e., any witness for $f(w)$'s membership in $B$ can be converted back into a witness for $w$'s membership in $A$. Both directions are required; proving only one is the most common flaw in student-constructed reductions.

Step 6 — Verify the time bound. Confirm that $f$ runs in time polynomial in $|w|$ — usually immediate from the construction being a simple syntactic transformation (loop over clauses, loop over vertices, etc.). ``` // Generic template for constructing and using a mapping reduction function REDUCE_A_TO_B(w): // w is an instance of A // Step 2/3: build instance of B using a gadget construction instance_B = build_gadget(w) return instance_B function DECIDE_A_VIA_B(w, DecideB): // DecideB solves B instance_B = REDUCE_A_TO_B(w) return DecideB(instance_B) // correct because // w in A <=> instance_B in B // Correctness obligations that must be proven separately: // (1) forward: w in A ==> build_gadget(w) in B // (2) backward: w not in A ==> build_gadget(w) not in B // (3) time: build_gadget runs in poly(|w|) steps ``` To make this concrete, consider a reduction from 3SAT (Boolean formulas in conjunctive normal form with exactly three literals per clause) to CLIQUE (does a graph $G$ have a clique — a fully connected subgraph — of size $k$?). This is the canonical reduction that foreshadows Classic NP-Complete Problems: Clique and Vertex Cover. Given a 3CNF formula $\phi$ with $k$ clauses $c_1, \dots, c_k$, each containing three literals, build a graph $G$ as follows: create one vertex for each literal occurrence (so up to $3k$ vertices total, grouped into $k$ triples, one triple per clause). Connect two vertices with an edge if and only if they come from different clauses and they are not negations of each other (i.e., they are not a literal and its logical complement). Set the target clique size to $k$, one vertex per clause. ``` function REDUCE_3SAT_TO_CLIQUE(phi): // phi has clauses c_1..c_k, 3 literals each G = empty graph for i in 1..k: for each literal L in clause c_i: add vertex (i, L) to G for i in 1..k: for j in 1..k, j != i: for literal L1 in clause c_i: for literal L2 in clause c_j: if L1 is not the negation of L2: add edge between (i, L1) and (j, L2) return (G, k) // instance of CLIQUE ``` This loop structure has $O(k^2)$ vertex pairs to examine (each clause has a constant 3 literals), so the whole construction runs in $O(k^2)$ time — polynomial in the size of $\phi$.

Time complexity of the reduction itself. For the 3SAT-to-CLIQUE gadget, the input formula has $k$ clauses and $3k$ literal occurrences. The construction allocates one vertex per literal occurrence ($O(k)$ vertices) and checks every pair of literals from different clauses for compatibility ($O((3k)^2) = O(k^2)$ pairs, each check taking constant time to compare a literal against its negation). Total time is $O(k^2)$, which is polynomial in the input size $|\phi| = O(k)$. This is what makes it a polynomial-time mapping reduction rather than merely a mapping reduction (an important distinction, since unrestricted mapping reductions computable by any Turing machine — even exponential-time ones — are too weak to preserve efficient solvability).

Space complexity. The constructed graph has $O(k)$ vertices and $O(k^2)$ edges, so it requires $O(k^2)$ space to write down — again polynomial, and in fact this bounds the reduction's time from below too, since it must write every edge.

Correctness — the forward direction. Suppose $\phi$ is satisfiable, with satisfying assignment $\alpha$. In each clause $c_i$, at least one literal is made true by $\alpha$; pick one such literal and call its vertex $v_i$. Claim: $\{v_1, \dots, v_k\}$ forms a $k$-clique in $G$. Any two chosen vertices $v_i, v_j$ ($i \ne j$) come from different clauses, satisfying the first edge condition. They also cannot be negations of each other, because both literals are made true by the same assignment $\alpha$, and a literal and its negation can never both be true under one assignment. Hence every pair of chosen vertices is connected, giving a clique of size exactly $k$.

Correctness — the backward direction. Suppose $G$ has a clique of size $k$. Since vertices within the same clause-triple are never connected (only cross-clause edges exist), the clique must contain exactly one vertex from each of the $k$ clause-groups — otherwise it could not reach size $k$ using at most $3$ vertices "sharing" the same clause and being mutually non-adjacent. Define an assignment $\alpha$ that sets each literal in the clique to true (and freely fixes any variables not mentioned by the clique in either polarity). This is consistent — no variable is asked to be both true and false — precisely because two vertices representing a literal and its negation are never joined by an edge, so a clique can never contain such a contradictory pair. Under $\alpha$, every clause has its chosen literal satisfied, so $\alpha$ satisfies $\phi$. Together, these two directions establish the biconditional $\phi \in \text{3SAT} \iff (G, k) \in \text{CLIQUE}$, exactly the defining property of a mapping reduction.

Why this matters for hardness transfer. Suppose (hypothetically) CLIQUE had a polynomial-time decision algorithm $D$. Then 3SAT could be decided in polynomial time too: transform $\phi$ into $(G,k)$ in $O(k^2)$ time, then run $D$ on $(G,k)$, which by assumption takes time polynomial in the size of $(G,k)$ — itself polynomial in $|\phi|$. Composing two polynomials is a polynomial, so 3SAT $\in P$ would follow. Since 3SAT is NP-complete (via Cook–Levin plus further reductions), this would imply $\mathrm{P} = \mathrm{NP}$. This is the exact logical template used, over and over, to show new problems are NP-complete — construct a reduction from a known NP-complete problem, and hardness transfers automatically.

Honesty about limits. A mapping reduction only ever moves hardness or easiness in one direction along the arrow $A \le_p B$; it says nothing about the converse relation $B \le_p A$, which may or may not hold. Mapping reductions are also strictly weaker than general (Turing) reductions — every mapping reduction can be simulated by a Turing reduction, but not vice versa — so a failure to find a mapping reduction between two problems does not prove they are unrelated in difficulty by other means.

Let's trace the reduction on a concrete, small 3CNF formula:

This is exactly the formula depicted in the figure above, with $k = 3$ clauses, so the reduction asks for a clique of size $3$.

Now check satisfiability directly: try $\alpha = (x_1 = \text{true}, x_2 = \text{true}, x_3 = \text{true})$.

• $c_1 = (x_1 \lor x_2 \lor \lnot x_3)$: $x_1$ true → clause satisfied. Chosen literal-vertex: $x_1$ in $c_1$.
• $c_2 = (\lnot x_1 \lor x_2 \lor x_3)$: $x_2$ true → clause satisfied. Chosen literal-vertex: $x_2$ in $c_2$.
• $c_3 = (x_1 \lor \lnot x_2 \lor x_3)$: $x_1$ true → clause satisfied. Chosen literal-vertex: $x_1$ in $c_3$.

Following the proof: the three chosen vertices are $\{x_1 \text{ in } c_1,\ x_2 \text{ in } c_2,\ x_1 \text{ in } c_3\}$. Check all three pairs for edges:

• $x_1(c_1)$ — $x_2(c_2)$: different clauses, not negations → edge exists. ✓
• $x_1(c_1)$ — $x_1(c_3)$: different clauses, not negations (same literal, not a contradiction) → edge exists. ✓
• $x_2(c_2)$ — $x_1(c_3)$: different clauses, not negations → edge exists. ✓

All three pairs are mutually adjacent — this is the highlighted triangle (a $3$-clique) in the figure, exactly as the forward-direction proof guarantees. Running the (hypothetical) polynomial-time CLIQUE decider on $(G,3)$ returns yes, and the composed algorithm correctly reports that $\phi$ is satisfiable — without ever running a SAT solver directly.

Richard Karp's 1972 paper is arguably the single most influential demonstration of the power of mapping reductions: rather than proving each problem's hardness from scratch, he built a web of reductions radiating out from Cook's satisfiability result, instantly certifying dozens of practically important problems — including Clique, Vertex Cover, Hamiltonian Cycle, and Set Cover — as NP-complete. This methodology, chaining reductions from a known-hard "seed" problem, remains the standard technique taught today and is precisely the tool used when introducing Classic NP-Complete Problems: Clique and Vertex Cover.

Polynomial-time mapping reductions are the connective tissue of complexity theory, but their impact reaches directly into engineering practice. SAT and SMT solvers (used in hardware verification at companies building CPUs and in software model checking) are powerful precisely because so many practical problems — scheduling, resource allocation, formal equivalence checking — have known polynomial-time reductions into SAT, letting engineers reuse a single highly optimized solver instead of building bespoke algorithms for every new problem. Integer linear programming solvers play the same role for operations-research problems like routing and packing. Compiler register allocation is classically reduced to graph coloring; database query optimization and constraint satisfaction in AI planning both lean on reduction-based reasoning to decide which subproblems are tractable. Every time a new problem is shown NP-complete via a fresh reduction, the entire toolbox of approximation algorithms, heuristics, and SAT/ILP encodings developed for existing NP-complete problems becomes available for it — this is the deepest practical payoff of the reduction framework, and it is the reasoning that will be used immediately when NP-Completeness is formalized and specific problems such as Clique and Vertex Cover are proven complete.

Ask the tutor: How does this reduction framework extend to prove Vertex Cover and Hamiltonian Cycle are NP-complete once Clique is established?