Exercises — NP-completeness — Cook's theorem (SAT is NP-complete), reduction

(a) In NP: a "yes" instance has a certificate (a guessed solution) that can be checked by a deterministic machine in polynomial time. See Verifier definition of NP. (b) NP-hard: every problem $L\in$ NP reduces to $X$ by a polynomial-time reduction ($L{\le }_{p}X$ for all such $L$). "At least as hard as everything in NP." (c) NP-complete: $X$ is in NP and $X$ is NP-hard. The hardest problems that still live inside NP.

$B$ is at least as hard as $A$. Reason: if you had a fast solver for $B$, you could solve any instance $x$ of $A$ by computing $f(x)$ (cheap) and asking your $B$-solver. So $B$'s power ≥ $A$'s power. See Polynomial-time reduction.

(1) SAT $\in$ NP — given a truth assignment, plug in and evaluate $\varphi$ in poly time. (2) SAT is NP-hard — every $L\in$ NP reduces to SAT (the tableau construction). Both together = NP-complete.

Try $x_3=\text{TRUE}$. Then $x_3$ appears (positively) in both clauses, so both are satisfied regardless of $x_1,x_2$. One satisfying assignment: $x_1=\text{FALSE},x_2=\text{FALSE},x_3=\text{TRUE}$. Check: clause 1 $=(\text{F}\vee \text{T}\vee \text{T})=\text{T}$; clause 2 $=(\text{T}\vee \text{F}\vee \text{T})=\text{T}$. So $\varphi =\text{TRUE}$. Satisfiable. ✔

The split is $({\ell }_1\vee {\ell }_2\vee y)\wedge (\neg y\vee {\ell }_3\vee {\ell }_4).$ Here $y$ is a brand-new variable, not appearing anywhere else. We claim: there is a way to assign $y$ that makes both new clauses true if and only if at least one of ${\ell }_1,{\ell }_2,{\ell }_3,{\ell }_4$ is true (which is exactly what the original clause demands).

Direction 1 — original true $\Rightarrow$ split satisfiable. Suppose some ${\ell }_i$ is true. There are two cases:

• If ${\ell }_1$ or ${\ell }_2$ is true, set $y=\text{FALSE}$. Then clause 1 is true (via ${\ell }_1$ or ${\ell }_2$), and clause 2 is true because $\neg y=\text{TRUE}$. ✔
• If instead ${\ell }_3$ or ${\ell }_4$ is true, set $y=\text{TRUE}$. Then clause 1 is true because $y=\text{TRUE}$, and clause 2 is true (via ${\ell }_3$ or ${\ell }_4$). ✔ Either way we found a value of $y$ making both clauses true.

Direction 2 — split satisfiable $\Rightarrow$ original true. Suppose both new clauses are true for some choice of $y$. Look at the value of $y$:

• If $y=\text{TRUE}$, then clause 2 $(\neg y\vee {\ell }_3\vee {\ell }_4)$ has $\neg y=\text{FALSE}$, so it is true only if ${\ell }_3$ or ${\ell }_4$ is true.
• If $y=\text{FALSE}$, then clause 1 $({\ell }_1\vee {\ell }_2\vee y)$ has $y=\text{FALSE}$, so it is true only if ${\ell }_1$ or ${\ell }_2$ is true. In either case at least one original literal is true, so the original clause is true. ✔

Both directions give the iff. In particular, if all four ${\ell }_i$ are false: clause 1 forces $y=\text{TRUE}$, clause 2 forces $y=\text{FALSE}$ — a contradiction, so the split is unsatisfiable, matching the original. This is the 3-SAT clause-splitting reduction.

First recall the two ingredients (built here so you need nothing external). An independent set is a collection of graph vertices with no edge between any two of them. The construction turns each clause into a triangle (3 mutually-connected vertices, one per literal) and joins two vertices by a conflict edge whenever they are complementary literals ($x_i$ with $\neg x_i$). See Independent Set.

Counts for this formula:

• Vertices: one per literal-occurrence $=3$ literals $\times 2$ clauses $=6$.
• Target: $k=m=$ number of clauses $=2$.

The figure below shows the exact graph. Read it top-to-bottom: the two blue triangles are the two clauses; the two red dashed lines are the conflicts $x_1$–$\neg x_1$ and $\neg x_2$–$x_2$. Notice the third literal of each clause is $x_3$, appearing on both sides with no conflict edge between them, because $x_3$ and $x_3$ are the same literal, not complementary.

Why an independent set of size $k=m$ forces exactly one true literal per clause:

• Each triangle has 3 vertices, all mutually adjacent. An independent set may contain at most one vertex from any triangle (two vertices of a triangle are always joined). So across $m$ triangles you can pick at most $m$ vertices total. To reach the target $k=m$, you must pick exactly one vertex from every triangle — no clause is skipped.
• The chosen vertex in a triangle names one literal of that clause; declare that literal TRUE. Because we picked one per triangle, every clause gets a true literal, so the formula is satisfied.
• The conflict edges stop this assignment from being contradictory: since $x_i$ and $\neg x_i$ are joined, an independent set can never contain both, so we never simultaneously declare $x_i$ true and $\neg x_i$ true. The assignment is consistent.

Conversely, a satisfying assignment picks, in each clause, one literal it made true, and those chosen vertices form an independent set of size $m$ (same-triangle pairs excluded by the triangle, complementary pairs excluded by consistency). This is the two-way correspondence that makes the reduction correct.

A Turing machine changes only the cell under the head and, via head movement, its immediate neighbour in a single step. So legality of "row $i$ leads to row $i+1$" is a property of small horizontal neighbourhoods. If every window of 2 rows × 3 columns is consistent with the transition rules, then, cell by cell, each row correctly follows from the one above — hence the entire tableau is a legal run.

The count. The tableau has $p(n)+1$ time-rows and $p(n)+1$ tape-columns. A $2\times 3$ window is fixed by choosing its top-left corner: any of the first $p(n)$ rows (so the window's second row still exists) and any of the first $p(n)-1$ columns (so all three columns exist). That is at most $p(n)\cdot (p(n)-1)=O(p(n{)}^2)$ windows. For each window we AND in a bounded set of clauses — one forbidding each illegal content-pattern of that window — and the number of possible patterns is a constant (it depends only on the fixed alphabet and state set of $M$, not on $n$). So total window-clauses $=O(p(n{)}^2)\times \text{const}=O(p(n{)}^2)$. Polynomial. ✔

The tableau is $(p(n)+1)\times (p(n)+1)$ — one dimension for time steps, one for tape cells. That product gives the $p(n{)}^2$ grid positions (the square). For each position we have one variable per possible content $s$: each tape symbol, plus each (state, "head here") pairing. The alphabet and state set are fixed for the machine $M$, independent of input length $n$ — that fixed count is the constant. Total: $O(p(n{)}^2)\cdot (\text{const})$.

Let $f$ reduce $A$ to $B$ and $g$ reduce $B$ to $C$, both poly-time. Define $h(x)=g(f(x))$. (Recall $|x|$ is the length of the string $x$, and "poly-time" means the step-count is at most $|x|$ multiplied by itself a fixed number of times.)

• Correctness: $x\in A⟺f(x)\in B⟺g(f(x))\in C$, i.e. $x\in A⟺h(x)\in C$. ✔
• Poly-time: say $f$ runs in at most $|x{|}^a$ steps for some fixed whole number $a$ (input length raised to the power $a$). Since $f$ cannot write more symbols than steps it takes, its output length satisfies $|f(x)|\le |x{|}^a$. Now $g$ runs in at most $|f(x){|}^b$ steps for some fixed $b$, and $|f(x){|}^b\le (|x{|}^a{)}^b=|x{|}^{ab}$ — the input length raised to the fixed power $a\cdot b$. That is still a fixed power of $|x|$, so $h$ is poly-time. ✔

Why essential: Cook gives "everything in NP ${\le }_p$ SAT." To crown a new problem $B$ NP-complete we only show SAT (or another known NP-complete $A$) ${\le }_{p}B$. Transitivity then chains "everything ${\le }_{p}A$" with "$A{\le }_{p}B$" to yield "everything ${\le }_{p}B$" — without transitivity, one reduction wouldn't inherit the hardness of all of NP. See Karp's 21 NP-complete problems.

First, definitions built here. A vertex cover of a graph $G=(V,E)$ is a set of vertices $C$ such that every edge has at least one endpoint in $C$ — the vertices "cover" all edges. Recall an independent set is a set with no edge inside it. See Vertex Cover.

Key fact: $S$ is an independent set iff its complement $V\setminus S$ is a vertex cover. Reason: no edge lies inside $S$ $⟺$ every edge has at least one endpoint outside $S$, i.e. in $V\setminus S$.

Reduction $f$: given an IS-instance $(G,k)$ (does $G$ have an independent set of size $\ge k$?), output the Vertex-Cover instance $(G,|V|-k)$ — same graph, complementary target. This is clearly polynomial-time: we copy the graph and compute one subtraction.

The iff: $G$ has an independent set of size $\ge k$ $⟺$ $G$ has a vertex cover of size $\le |V|-k$.

• ($\Rightarrow$) An independent set $S$ with $|S|\ge k$ gives cover $V\setminus S$ of size $|V|-|S|\le |V|-k$.
• ($\Leftarrow$) A vertex cover $C$ with $|C|\le |V|-k$ gives independent set $V\setminus C$ of size $|V|-|C|\ge k$.

The figure makes the complement concrete: on a small graph, the green vertices form an independent set and the leftover orange vertices form a vertex cover.

Read the figure: the green pair $\{a,c\}$ has no edge between them (independent, size $2$); the orange pair $\{b,d\}$ is exactly the leftover, and you can check every drawn edge touches an orange vertex (cover, size $|V|-2=2$). This visual is the "complement" fact.

Since IS ${\le }_p$ Vertex Cover and IS is NP-complete, Vertex Cover is NP-hard. (The exercise stops here — we were only asked for NP-hardness, not the extra membership-in-NP argument.)

Definition built here: a clique is a set of vertices with an edge between every pair (a fully-connected group). The complement graph $\bar{G}$ has the same vertices as $G$ but swaps edges and non-edges: two vertices are adjacent in $\bar{G}$ iff they were non-adjacent in $G$. See Clique.

Key fact: a set $S$ is an independent set in $G$ (no edges inside $S$) iff $S$ is a clique in $\bar{G}$ (all pairs inside $S$ are edges of $\bar{G}$). This is immediate: "no edge in $G$ among $S$" becomes "every non-edge, i.e. every $\bar{G}$-edge, present among $S$."

Reduction $f$: given IS-instance $(G,k)$, output Clique-instance $(\bar{G},k)$. Building $\bar{G}$ examines each of the at most $|V{|}^2$ vertex pairs once, so $f$ is polynomial-time.

The iff: $G$ has an independent set of size $\ge k$ $⟺$ $\bar{G}$ has a clique of size $\ge k$ (same vertex set works, same $k$).

Therefore IS ${\le }_p$ Clique, and since IS is NP-complete, Clique is NP-hard.

Not valid. A reduction must be computable in polynomial time. Writing down a graph with $2^n$ vertices requires at least $2^n$ steps just to output it — that is exponential, not polynomial. So the map $f$ fails the poly-time requirement, and the chain of hardness is broken (see the parent note's last mistake callout). A correct SAT/3-SAT $\to$ IS reduction produces $O(\text{clauses})$ vertices, which is polynomial in the input size.

• Empty formula (a conjunction of zero clauses): vacuously TRUE, so satisfiable — the empty AND is TRUE by convention.
• Empty clause $()$ (a disjunction of zero literals): FALSE, so any formula containing it is unsatisfiable — the empty OR is FALSE. Why it matters: a reduction $f$ must satisfy $x\in \text{SAT}⟺f(x)\in B$ for every instance, including these edge cases. In the 3-SAT $\to$ IS reduction, the empty formula maps to a graph with $0$ triangles and target $k=0$; an independent set of size $0$ trivially exists — consistent with "satisfiable." If your construction crashed or gave the wrong answer on zero clauses, the iff fails and the reduction is wrong.

Two different tasks are being conflated:

• Constructing the formula ${\varphi }_{M,w}$ from $(M,w)$ is poly-time. That is what Cook's reduction does.
• Solving SAT — deciding whether ${\varphi }_{M,w}$ is satisfiable — is the (believed) hard part. No known poly-time algorithm does this.

Building a hard question quickly is not the same as answering it quickly. The reduction moves the difficulty into SAT; it does not dissolve it. Whether SAT (and hence all of NP) can be solved in poly time is precisely the open P vs NP problem. So the conclusion is unwarranted.

Direction of a hardness reduction ::: reduce FROM a known NP-complete problem INTO your new problem ($A{\le }_{p}B$ makes $B$ hard). SAT satisfiability of the empty formula ::: TRUE (vacuous conjunction), so satisfiable. SAT satisfiability of a formula containing the empty clause ::: FALSE (vacuous disjunction), unsatisfiable.