Theory of Computation: Lecture 8

Polynomial-Time Reductions

NP membership says that yes-instances have short certificates that can be checked quickly. NP-completeness needs a second idea: translate one decision problem into another without losing the yes/no answer and without spending more than polynomial time.

Polynomial-time computable function. A function $f:\Sigma^*\to\Sigma^*$ is polynomial-time computable if some polynomial-time Turing machine halts on every input $w$ with exactly $f(w)$ on its tape.

The function must be total. It must produce an output for every input, even when the input is a no-instance.

Polynomial-time mapping reduction. A language $A$ is polynomial-time mapping reducible to a language $B$, written $A\le_P B$, if there is a polynomial-time computable function $f:\Sigma^*\to\Sigma^*$ such that, for every string $w$,

$$w\in A \quad\Longleftrightarrow\quad f(w)\in B.$$

• Computability. The instance $f(w)$ can be constructed in polynomial time.
• Correctness. The translation preserves membership exactly.
• Surjectivity. Not required. Some instances of $B$ may never be produced by $f$.

The direction $A\le_P B$ means: a fast solver for $B$ would give a fast solver for $A$. So $B$ is at least as hard as $A$.

Theorem. If $A\le_P B$ and $B\in P$, then $A\in P$.

Proof. Let $f$ be a polynomial-time reduction from $A$ to $B$, and let $M_B$ be a polynomial-time decider for $B$. Build a decider $N$ for $A$:

1. On input $w$, compute $f(w)$.
2. Run $M_B$ on $f(w)$.
3. Output whatever $M_B$ outputs.

The machine $N$ decides $A$ because

$$N\text{ accepts }w \quad\Longleftrightarrow\quad M_B\text{ accepts }f(w) \quad\Longleftrightarrow\quad f(w)\in B \quad\Longleftrightarrow\quad w\in A.$$

Cost rule. If $f$ runs in $O(n^q)$ time and $M_B$ runs in $O(n^p)$ time, then $|f(w)|=O(|w|^q)$ because the reduction cannot write more symbols than its running time allows. The composed decider runs in

$$O(|w|^q)+O(|f(w)|^p) = O(|w|^q+|w|^{pq}) = O(|w|^{pq})$$

for fixed constants $p,q\ge 1$.

Corollary. If $A\le_P B$ and $A\notin P$, then $B\notin P$.

This is a hardness transfer. For NP problems, however, we usually do not know that a natural language is outside $P$. NP-completeness replaces that missing knowledge with reductions from all of $NP$.

Transitivity of polynomial-time reductions. If $A\le_P B$ and $B\le_P C$, then $A\le_P C$.

If $f_{AB}$ runs in $O(n^p)$ time and $f_{BC}$ runs in $O(n^q)$ time, the composed map $w\mapsto f_{BC}(f_{AB}(w))$ is polynomial-time computable. Correctness follows by chaining the two equivalences:

$$w\in A \quad\Longleftrightarrow\quad f_{AB}(w)\in B \quad\Longleftrightarrow\quad f_{BC}(f_{AB}(w))\in C.$$

NP-Complete Languages

NP-hard language. A language $H$ is NP-hard if every language in $NP$ polynomial-time reduces to it:

$$\forall L\in NP,\quad L\le_P H.$$

NP-complete language. A language $H$ is NP-complete if it is both in $NP$ and NP-hard.

• Membership. $H\in NP$, so yes-instances of $H$ have short certificates.
• Hardness. Every problem in $NP$ can be translated to $H$ in polynomial time.

If any NP-complete language has a polynomial-time decider, then $P=NP$: for every $L\in NP$, use $L\le_P H$ and the theorem above to get $L\in P$.

Cook-Levin theorem. $\mathrm{SAT}$ is NP-complete.

Thus $\mathrm{SAT}$ is the first complete problem: it is in $NP$, and every language in $NP$ reduces to it in polynomial time.

Recipe: proving that $L$ is NP-complete.

1. NP membership. Give a polynomial-time verifier for $L$.
2. NP-hardness. Reduce a known NP-complete language to $L$.
3. Conclusion. Since the known complete problem represents all of $NP$, transitivity gives every $A\in NP$ a reduction to $L$.

At the start, the known NP-complete language is $\mathrm{SAT}$. Later, any already proven NP-complete language may be used.

The 3SAT Reduction

$k$SAT. The language of satisfiable CNF formulas in which every clause contains at most $k$ literals.

With this convention, $3$SAT allows clauses of size $1$, $2$, or $3$.

Theorem. $3\mathrm{SAT}$ is NP-complete.

Membership in $NP$ is inherited from $\mathrm{SAT}$: a certificate is a truth assignment, and the verifier checks every clause.

For hardness, reduce $\mathrm{SAT}$ to $3\mathrm{SAT}$. Let $K$ be a clause with more than three literals:

$$K=(\ell_1\vee \ell_2\vee \ell_3\vee\cdots\vee \ell_m), \qquad m>3.$$

Introduce a fresh variable $z$ and replace $K$ by two clauses:

$$K_1=(\ell_1\vee \ell_2\vee z), \qquad K_2=(\neg z\vee \ell_3\vee\cdots\vee \ell_m).$$

This preserves satisfiability.

If $K$ is satisfiable and one of $\ell_1,\ell_2$ is true, set $z=\mathrm{false}$. Then $K_1$ is true because of the original true literal, and $K_2$ is true because of $\neg z$. If a true literal appears only among $\ell_3,\ldots,\ell_m$, set $z=\mathrm{true}$.

Conversely, if all original literals $\ell_1,\ldots,\ell_m$ are false, then $K_1$ forces $z=\mathrm{true}$ while $K_2$ forces $z=\mathrm{false}$, impossible. So any satisfying assignment for $K_1\wedge K_2$ makes at least one original literal true.

Repeat this replacement until every clause has at most three literals. Each step shortens one long clause by one literal, introduces one fresh variable, and increases the formula size only linearly. Therefore the whole transformation is polynomial time, and the resulting formula is satisfiable exactly when the original formula is satisfiable.

The same idea does not give a SAT-to-2SAT reduction: binary clauses cannot carry the remaining tail of a long disjunction in the same satisfiability-preserving way.

INDSET Is NP-Complete

Independent set language. The language

$$\mathrm{INDSET} = \{\langle G,k\rangle\mid G\text{ has an independent set of size }k\}.$$

Membership in $NP$ is immediate: a certificate is a set $S\subseteq V(G)$, and the verifier checks that $|S|=k$ and that no pair of vertices in $S$ is connected by an edge.

Theorem. $\mathrm{INDSET}$ is NP-complete.

It remains to prove NP-hardness by showing $\mathrm{SAT}\le_P\mathrm{INDSET}$.

Reduction from SAT to INDSET. Given a CNF formula $\varphi$ with clauses $K_1,\ldots,K_m$, build a graph $G$ as follows:

1. Create one vertex for each literal occurrence in each clause.
2. Add edges between every pair of vertices from the same clause.
3. Add edges between every pair of conflicting literals, such as $x_i$ and $\neg x_i$.
4. Output $\langle G,m\rangle$.

Each clause becomes a clique, so an independent set can select at most one literal per clause. Conflict edges prevent it from selecting inconsistent literals.

For example, for

$$\varphi = (\neg x_1) \wedge (x_1\vee \neg x_2) \wedge (x_1\vee x_2\vee \neg x_3) \wedge (x_1\vee x_2\vee x_3\vee \neg x_4),$$

the selected vertices correspond to the satisfying assignment $x_1=x_2=x_3=x_4=\mathrm{false}$.

Correctness: satisfiable formula gives independent set. Suppose $\varphi$ has a satisfying assignment. In each clause, choose one literal that is true. The chosen vertices form an independent set of size $m$: there is one chosen vertex per clause, so no same-clause edge is used, and two true literals under one assignment cannot be conflicting.

Correctness: independent set gives satisfying assignment. Suppose $G$ has an independent set $S$ of size $m$. Since each clause group is a clique, $S$ contains at most one vertex from each clause. There are $m$ clauses and $|S|=m$, so it contains exactly one vertex from every clause. Since $S$ has no conflict edge, the selected literals are mutually consistent. Set each selected literal to true and assign the remaining variables arbitrarily. Every clause has a selected true literal, so $\varphi$ is satisfiable.

The graph has one vertex per literal occurrence and at most quadratically many edges in the formula size, so the construction is polynomial time. Therefore $\mathrm{SAT}\le_P\mathrm{INDSET}$, and since $\mathrm{INDSET}\in NP$, the language is NP-complete.