Polynomial-Time Reductions

Transform one problem into another to compare their hardness.

The idea

A polynomial-time mapping reduction translates one decision problem into another, and it is the tool with which we compare the hardness of problems. A reduction from a language $A$ to a language $B$, written $A \le_{p} B$, is a function $f$ computable in polynomial time such that for every string $w$, $w \in A \iff f(w) \in B.$ The function solves neither problem; it converts a question about $A$ into a question about $B$ with the same yes-or-no answer. The figure shows both halves of the requirement: a string $w \in A$ is carried to $f(w) \in B$, and a string $w' \notin A$ is carried outside $B$.

Its two consequences run in opposite directions, and every hardness proof depends on stating the direction correctly. Tractability flows along the arrow: if $B$ is decidable in polynomial time, then so is $A$ — to decide $w \in A$, compute $f(w)$ and run the decider for $B$ on it. Hardness flows against the arrow: if $A$ is hard, then $B$ is hard, since a fast algorithm for $B$ would have made $A$ fast. To prove a new problem $B$ hard, we therefore reduce from the known-hard problem: we build $A \le_{p} B$, with the hard problem as the source, never the reverse.

The bookkeeping stays polynomial because a machine running in polynomial time writes only polynomially many symbols: $f(w)$ is at most polynomially longer than $w$, so a polynomial-time decider applied to it remains polynomial overall.

Ways to work on it

• Walkthrough. What a polynomial-time reduction is and which way it transfers hardness.
• Practice. Apply reduction composition and the direction of tractability and hardness.
• Hardest. Work through the 3SAT-to-CLIQUE reduction and count the graph it builds.

Not sure where to start? Take the ten-question placement test.