Polynomial-time reductions

◈ 6 cards

Define L₁ ≤ₚ L₂ via a poly-computable f with x ∈ L₁ ⇔ f(x) ∈ L₂; prove the key transfer lemma (L₂ ∈ P ⇒ L₁ ∈ P), see why ≤ₚ is transitive, and pin down NP-hard vs NP-complete.

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} \leq_{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} ⟺ 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} \leq_{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. $■$

The contrapositive is how we use it in practice: if $L_{1} \in / P$ (we believe it is hard) and $L_{1} \leq_{p} L_{2}$ , then $L_{2} \in / 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 \leq_{p} B (reduce the KNOWN-hard problem TO the new one) .$

Why this direction? $A \leq_{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 \leq_{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 $\overset{ˉ}{G}$ . So define $f (⟨ G, k ⟩) = ⟨ \overset{ˉ}{G}, k ⟩$ . Building $\overset{ˉ}{G}$ is $O (V^{2})$ — polynomial. And $G$ has a $k$ -clique $⟺ \overset{ˉ}{G}$ has an independent set of size $k$ . That is exactly CLIQUE $\leq_{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} \leq_{p} L_{2}$ and $L_{2} \leq_{p} L_{3}$ then $L_{1} \leq_{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 N P$ satisfies $L^{'} \leq_{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 N P$ 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 = N P$ (because every NP problem reduces to it, so by the transfer lemma all of NP would collapse into P). Equivalently, if $P \neq = N P$ , then no NP-complete problem has a polynomial-time algorithm.

The reduction machinery behind the transfer lemma: f runs in polynomial time and M₂ runs in polynomial time, so the composition M₁ = M₂ ∘ f decides L₁ in polynomial time.

Direction is the whole proof. CLIQUE ≤ₚ INDEPENDENT-SET puts the KNOWN-hard problem on the left, via f(⟨G,k⟩) = ⟨Ḡ,k⟩, so CLIQUE’s hardness flows into INDEPENDENT-SET. The reverse arrow only says INDEPENDENT-SET is no harder than something already hard — no information.