Polynomial-time reductions

Relating one problem to another

We rarely analyze a hard problem from scratch. Instead we reduce it to a problem we already understand. A polynomial-time reduction from language $L_1$ to language $L_2$, written

$$L_1 \le_p L_2,$$

is a polynomial-time computable function $f$ that maps every instance $x$ of $L_1$ to an instance $f(x)$ of $L_2$ such that

$$x \in L_1 \iff f(x) \in L_2.$$

In words: $f$ turns yes-instances into yes-instances and no-instances into no-instances, and it does so quickly. The function $f$ is called the reduction algorithm. Note both halves of the biconditional matter — a map that only preserved yes-instances would be useless.

The transfer lemma (the whole point)

Reductions are valuable because they transfer tractability backwards:

> Lemma. If $L_1 \le_p L_2$ and $L_2 \in P$, then $L_1 \in P$.

Proof. Suppose $f$ is the polynomial-time reduction and $M_2$ is a polynomial-time decider for $L_2$. Build a decider $M_1$ for $L_1$: on input $x$, compute $f(x)$ (polynomial time), then run $M_2$ on $f(x)$ and return its answer. Correctness is the biconditional: $M_1$ accepts $x$ iff $M_2$ accepts $f(x)$ iff $f(x) \in L_2$ iff $x \in L_1$. Running time: $f$ runs in time $O(|x|^a)$, so $|f(x)| = O(|x|^a)$ (it cannot write more than it has time for); then $M_2$ runs in time $O(|f(x)|^b) = O(|x|^{ab})$. The composition is polynomial. $\quad\blacksquare$

The contrapositive is how we use it in practice: if $L_1 \notin P$ (we believe it is hard) and $L_1 \le_p L_2$, then $L_2 \notin P$ either — the hardness of $L_1$ flows forward into $L_2$.

Direction is everything

This is the single most common student error. To prove a *new* problem $B$ is hard, you reduce a *known-hard* problem $A$ to $B$:

$$A \le_p B \qquad (\text{reduce the KNOWN-hard problem TO the new one}).$$

Why this direction? $A \le_p B$ says "if $B$ were easy, then $A$ would be easy too." Since we believe $A$ is *not* easy, $B$ cannot be easy. Reducing the *other* way ($B \le_p A$) would only tell you $B$ is no harder than the already-hard $A$ — which proves nothing about $B$ being hard.

Worked example — direction in action

Suppose CLIQUE is already known to be hard, and you want to show a new problem INDEPENDENT-SET is hard. An *independent set* in $G$ is a set of vertices with no edge between any two; a *clique* is a set with all edges present. They are duals under graph complement: $V'$ is a clique in $G$ iff $V'$ is an independent set in the complement graph $\bar G$. So define $f(\langle G, k\rangle) = \langle \bar G, k\rangle$. Building $\bar G$ is $O(V^2)$ — polynomial. And $G$ has a $k$-clique $\iff \bar G$ has an independent set of size $k$. That is exactly CLIQUE $\le_p$ INDEPENDENT-SET, with the *known-hard* CLIQUE on the left. Hardness flows into INDEPENDENT-SET.

Transitivity, NP-hard, and NP-complete

Reductions compose: if $L_1 \le_p L_2$ and $L_2 \le_p L_3$ then $L_1 \le_p L_3$ (run one reduction function then the other — still polynomial). This transitivity is what lets us build a *chain* of NP-complete problems from a single starting point.

Now the two definitions the exam lives on:

- $L$ is NP-hard if every language $L' \in NP$ satisfies $L' \le_p L$. (It is at least as hard as everything in NP — but $L$ itself need not be in NP.) - $L$ is NP-complete if (1) $L \in NP$ and (2) $L$ is NP-hard.

NP-complete problems are the *hardest problems in NP*. The payoff theorem: if any NP-complete problem is in P, then $P = NP$ (because every NP problem reduces to it, so by the transfer lemma all of NP would collapse into P). Equivalently, if $P \neq NP$, then no NP-complete problem has a polynomial-time algorithm.