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 $\iff$ some $y$ makes $A(x,y)=1$ $\iff 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 \lnot 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 $\varphi$ is satisfiable $\iff 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 $\langle G, k\rangle$ to $\langle \bar G, |V| - k\rangle$; $G$ has a $k$-clique $\iff \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 $\iff$ 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'$ and exhibit a reduction $L' \le_p L$: >   (a) define $f$ mapping instances of $L'$ to instances of $L$; >   (b) prove $f$ runs in polynomial time; >   (c) prove the biconditional $x \in L' \iff 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 $= \{\langle G, k\rangle : G$ has a vertex cover of size $k\}$.

Step 1 — in NP. Certificate: a set $V'$ of $k$ vertices. Verifier: check $|V'| = k$ and that every edge $(u,v)$ has $u \in V'$ or $v \in V'$. 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(\langle G, k\rangle) = \langle \bar G, |V| - k\rangle$.

- *(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'$ of size $k$ $\iff$ $V \setminus V'$ is a vertex cover of $\bar G$ of size $|V|-k$. Forward: if $V'$ is a clique in $G$ then no edge of $\bar G$ has both endpoints in $V'$, so every $\bar G$-edge touches $V \setminus V'$ — a cover. Reverse: if $V \setminus V'$ covers $\bar G$ then no $\bar G$-edge lies inside $V'$, so $V'$ is fully connected in $G$ — a clique.

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