NP-complete problems & how to prove one

Bootstrapping: the first NP-complete problem

The transfer lemma needs a seed — one problem proved NP-complete from first principles, before any reduction is available. That seed is CIRCUIT-SAT: given a boolean combinational circuit, is there an input assignment making the output $1$?

• In NP (Lemma 34.5): the certificate is an assignment of values to all wires; verify each gate is consistent with its inputs and the output wire is $1$ — $O(|C|)$.
• NP-hard (Lemma 34.6, Cook 1971): for any $L\in NP$ with poly-time verifier $A$ running in $T(n)=O(n^k)$ steps, build a circuit that simulates $A$ — lay down $T(n)$ copies of the small circuit $M$ computing one computation step, feeding each step's output into the next (a "time-unrolled" computer). The input $x$ and program are hardwired; only the certificate $y$ is left as free input. The resulting circuit is satisfiable $⟺$ some $y$ makes $A(x,y)=1$ $⟺x\in L$. The circuit has polynomial size, so this is a polynomial reduction. Hence $L{\le }_p$ CIRCUIT-SAT for every $L\in NP$ — CIRCUIT-SAT is NP-hard, and being in NP too, it is NP-complete.

The deep idea: a computer's hardware is a boolean circuit, so any polynomial computation can be "frozen" into a circuit. That single fact bootstraps the entire theory.

The reduction chain

From CIRCUIT-SAT, transitivity (Lesson 9.2) extends NP-completeness by a chain of reductions, each ${\le }_p$:

$$\text{CIRCUIT-SAT}\to \text{SAT}\to \text{3-CNF-SAT}\to \text{CLIQUE}\to \text{VERTEX-COVER}\to \text{HAM-CYCLE}\to \text{TSP},$$

with a branch $\text{3-CNF-SAT}\to \text{SUBSET-SUM}$. A few links worth knowing:

• CIRCUIT-SAT ${\le }_p$ SAT: give each wire a variable and each gate a clause $x_i\leftrightarrow (\text{function of inputs})$; the formula is the AND of all gate clauses with the output wire. Using a variable per wire (rather than substituting recursively) keeps the formula linear even when wires fan out — the naive substitution blows up exponentially.
• SAT ${\le }_p$ 3-CNF-SAT: parse the formula, introduce a variable per internal node, convert each small clause to CNF via truth tables, then pad short clauses to exactly 3 literals — a 2-literal clause $(l_1\vee l_2)$ becomes $(l_1\vee l_2\vee p)\wedge (l_1\vee l_2\vee \neg p)$, which is satisfiable under exactly the same assignments.
• 3-CNF-SAT ${\le }_p$ CLIQUE: for a formula with $k$ clauses, build a graph with a triple of vertices per clause (one per literal) and an edge between two literals in different clauses unless they are a variable and its negation. Then $\phi$ is satisfiable $⟺G$ has a $k$-clique (pick one true literal per clause — they are mutually consistent and in different triples, so they are pairwise adjacent).
• CLIQUE ${\le }_p$ VERTEX-COVER: map $⟨G,k⟩$ to $⟨\bar{G},|V|-k⟩$; $G$ has a $k$-clique $⟺\bar{G}$ has a vertex cover of size $|V|-k$ (the clique's complement covers every edge of $\bar{G}$).
• HAM-CYCLE ${\le }_p$ TSP: weight existing edges $0$ and missing edges $1$ on the complete graph; a tour of total cost $0$ exists $⟺$ a Hamiltonian cycle exists.

The 2-step proof template (drill this)

The exam asks you to prove a problem $L$ is NP-complete. There is a fixed recipe — Lemma 34.8:

> Step 1 — show $L\in$ NP. Describe a polynomial-length certificate and a polynomial-time verifier that checks it. > > Step 2 — show $L$ is NP-hard. Pick a known NP-complete problem $L^{\prime }$ and exhibit a reduction $L^{\prime }{\le }_{p}L$: >   (a) define $f$ mapping instances of $L^{\prime }$ to instances of $L$; >   (b) prove $f$ runs in polynomial time; >   (c) prove the biconditional $x\in L^{\prime }⟺f(x)\in L$ — both directions. > > $L\in$ NP and NP-hard $\Rightarrow$ $L$ is NP-complete.

Worked example — proving VERTEX-COVER NP-complete

We run the template end to end on VERTEX-COVER $=\{⟨G,k⟩:G$ has a vertex cover of size $k\}$.

Step 1 — in NP. Certificate: a set $V^{\prime }$ of $k$ vertices. Verifier: check $|V^{\prime }|=k$ and that every edge $(u,v)$ has $u\in V^{\prime }$ or $v\in V^{\prime }$. That is $O(V+E)$, polynomial. So VERTEX-COVER $\in$ NP.

Step 2 — NP-hard via CLIQUE ${\le }_p$ VERTEX-COVER. Known-hard problem: CLIQUE (left side, correct direction). Reduction $f(⟨G,k⟩)=⟨\bar{G},|V|-k⟩$.

• (a) the map: build the complement graph $\bar{G}$ (edge present iff absent in $G$), keep $|V|-k$.
• (b) polynomial: constructing $\bar{G}$ is $O(V^2)$.
• (c) biconditional: $G$ has a clique $V^{\prime }$ of size $k$ $⟺$ $V\setminus V^{\prime }$ is a vertex cover of $\bar{G}$ of size $|V|-k$. Forward: if $V^{\prime }$ is a clique in $G$ then no edge of $\bar{G}$ has both endpoints in $V^{\prime }$, so every $\bar{G}$-edge touches $V\setminus V^{\prime }$ — a cover. Reverse: if $V\setminus V^{\prime }$ covers $\bar{G}$ then no $\bar{G}$-edge lies inside $V^{\prime }$, so $V^{\prime }$ is fully connected in $G$ — a clique.

Both conditions hold, so VERTEX-COVER is NP-complete. $■$ That four-line skeleton — certificate; pick known-NPC; map; poly; both directions — is the answer to nearly every NP-completeness exam question.