NP-completeness — Cook's theorem (SAT is NP-complete), reduction: Worked examples

Throughout, remember the one symbol we lean on: $A \leq_{p} B$ means "there is a polynomial-time function $f$ turning every instance $x$ of $A$ into an instance $f (x)$ of $B$ with $x \in A ⟺ f (x) \in B$ ." Read it out loud as " $B$ is at least as hard as $A$ ."

The scenario matrix

Think of "cases" here the way trig has quadrants. In reductions the axes are: what the input formula does (satisfiable / unsatisfiable / degenerate) and what task we are performing (verify membership, build a reduction, pick the direction). Every cell must have a worked example.

Cell	Scenario class	Degenerate / edge?	Covered by
C1	SAT instance that is satisfiable — find & verify certificate	no	Ex 1
C2	SAT instance that is unsatisfiable — prove NO by exhaustion	no	Ex 2
C3	Empty / trivial formulas (empty clause, empty formula)	yes, zero-input	Ex 3
C4	3-SAT $\to$ Independent Set on a satisfiable formula (build graph)	no	Ex 4 (figure)
C5	Same reduction on an unsatisfiable formula — why no large IS exists	no	Ex 5 (figure)
C6	SAT $\to$ 3-SAT clause splitting, incl. short (1- and 2-literal) clauses	edge: tiny clauses	Ex 6
C7	Direction trap — the exam classic "reduce which way?"	conceptual twist	Ex 7
C8	Chaining reductions via transitivity (3-SAT $\to$ IS $\to$ Vertex Cover)	composite	Ex 8 (figure)
C9	Real-world word problem — course scheduling as a SAT check	applied	Ex 9

The four clause-shapes to watch: a clause with 3 literals (normal), 2 literals, 1 literal, and the empty clause. Ex 3 and Ex 6 together cover all four.

The examples

Worked example Ex 1 — (C1) A satisfiable formula: produce the certificate

Statement. Is $ϕ = (x_{1} \lor \neg x_{2}) \land (x_{2} \lor x_{3}) \land (\neg x_{1} \lor \neg x_{3})$ satisfiable? If yes, give an assignment and verify it.

Forecast: guess now — do you think a truth assignment exists? (Three variables, so only 8 rows to try.)

Read what each clause demands. Clause 1 wants $x_{1}$ true OR $x_{2}$ false. Clause 2 wants $x_{2}$ true OR $x_{3}$ true. Clause 3 wants $x_{1}$ false OR $x_{3}$ false. Why this step? A formula is an AND of clauses, so it is TRUE only when every clause is TRUE. Reading demands one clause at a time turns the search into a small logic puzzle.
Try $x_{1} = T$ . Then clause 3 forces $x_{3} = F$ . Then clause 2 forces $x_{2} = T$ . Then clause 1: $x_{1}$ true — satisfied. Why this step? Fixing one variable propagates constraints, collapsing 8 possibilities fast (this is the idea behind real SAT solvers).
Assignment found: $x_{1} = T, x_{2} = T, x_{3} = F$ .

Verify: Clause 1 $= (T \lor F) = T$ . Clause 2 $= (T \lor F) = T$ . Clause 3 $= (F \lor T) = T$ . All TRUE ⇒ $ϕ = T$ . This is exactly the poly-time verification that puts SAT in NP: given the certificate, plug in and evaluate. ✔

Worked example Ex 2 — (C2) An unsatisfiable formula: proving NO

Statement. Is $ψ = (x) \land (\neg x \lor y) \land (\neg y) \land (x \lor y)$ satisfiable?

Forecast: clause $(x)$ alone is a strong hint. Guess YES or NO before reading.

Unit clauses force values. Clause $(x)$ has one literal, so $x$ must be TRUE. Clause $(\neg y)$ forces $y = F$ . Why this step? A single-literal ("unit") clause has no freedom — it dictates its variable. Always resolve those first.
Check the remaining clauses under $x = T, y = F$ . Clause $(\neg x \lor y) = (F \lor F) = F$ . Why this step? Once forced values exist, we only need to test whether any clause is now violated — no need to try other rows.
A clause is false ⇒ no assignment can satisfy $ψ$ . So $ψ$ is unsatisfiable.

Verify: The only candidate consistent with the two unit clauses is $x = T, y = F$ , and it fails clause 2. There is no other candidate, so exhaustion is complete. In Cook-tableau language: $ϕ_{M, w}$ being unsatisfiable corresponds to " $M$ has no accepting run" — a definite NO. ✔

Worked example Ex 3 — (C3) Degenerate inputs: empty clause and empty formula

Statement. What is the satisfiability of (a) the empty formula (no clauses at all), and (b) a formula containing the empty clause $()$ ?

Forecast: one of these is always true, the other is always false. Which is which?

Empty formula. An AND over zero clauses is the "empty AND". Why this step? Just as an empty product of numbers is $1$ , an empty AND is the identity of AND, which is TRUE. Nothing is demanded, so nothing can fail. → Always satisfiable (vacuously). Any assignment works, even over zero variables.
Empty clause $()$ . A clause is an OR of its literals; here the OR is over zero literals. Why this step? An empty OR is the identity of OR, which is FALSE. There is no literal that could rescue it. → A formula containing $()$ is always unsatisfiable, because that one clause is stuck at FALSE and the whole AND collapses.

Verify: Consistency check — TRUE is the identity for AND ( $p \land T = p$ ) and FALSE is the identity for OR ( $p \lor F = p$ ). Empty AND $\to$ T, empty OR $\to$ F, matching steps 1–2. These edge cases matter: reductions must not accidentally emit an empty clause when a clause "should" be satisfied. ✔

Worked example Ex 4 — (C4)

3-SAT $\to$ Independent Set, satisfiable case Statement. Build the Independent-Set graph for $ϕ = (x_{1} \lor \neg x_{2} \lor x_{3}) \land (\neg x_{1} \lor x_{2} \lor x_{3})$ , with target $k = m = 2$ . Find an independent set of size 2 and read off a satisfying assignment.

Forecast: two clauses ⇒ two triangles ⇒ 6 vertices. How many "conflict" edges between the triangles do you expect?

One triangle per clause. Clause 1 → vertices ${x_{1}, \neg x_{2}, x_{3}}$ ; clause 2 → ${\neg x_{1}, x_{2}, x_{3}}$ . Connect the three vertices inside each clause into a triangle. Why this step? A triangle means any independent set can grab at most one vertex of it — modelling "pick one literal to satisfy this clause".
Add conflict edges between complementary literals. $x_{1}$ — $\neg x_{1}$ and $\neg x_{2}$ — $x_{2}$ get edges (the blue dashed lines in the figure). Why this step? An independent set cannot take both endpoints of an edge, so we can never set a variable TRUE and FALSE at once — the assignment stays consistent.
Pick one vertex per triangle avoiding all edges. Take $x_{3}$ from triangle 1 and $x_{3}$ from triangle 2 — but those are two different vertices (one per clause) both labelled by literal $x_{3}$ , and no conflict edge joins them (same literal, not complementary). That is an independent set of size 2. Why this step? Size $= m = 2$ means "every clause got a satisfied literal".
Read off assignment. Chosen literals: $x_{3}$ and $x_{3}$ ⇒ set $x_{3} = T$ ; $x_{1}, x_{2}$ free (say F, F).

Verify: Under $x_{3} = T$ : clause 1 $= (\dots \lor T) = T$ , clause 2 $= (\dots \lor T) = T$ . Satisfiable ✔, and the IS we found has size exactly $k = 2$ ✔. Direction is correct: we reduced FROM 3-SAT (known hard) TO Independent Set. ✔

Worked example Ex 5 — (C5) Same reduction, unsatisfiable case: why no size-

$m$ IS Statement. Consider $ϕ = (x) \land (\neg x)$ — two clauses, so pad each to 3 literals by repetition: $(x \lor x \lor x) \land (\neg x \lor \neg x \lor \neg x)$ . Build the graph, $k = 2$ . Show there is no independent set of size 2.

Forecast: $ϕ$ is obviously unsatisfiable ( $x$ and $\neg x$ can't both hold). What must go wrong in the graph?

Triangle 1 = three copies of literal $x$ ; triangle 2 = three copies of literal $\neg x$ . Why this step? Repetition keeps clauses at 3 literals without changing meaning — a legal 3-SAT input.
Conflict edges: every $x$ -vertex joins every $\neg x$ -vertex. Since $x$ and $\neg x$ are complementary, all $3 \times 3 = 9$ cross edges appear (pink lines). Why this step? Complementary literals are always joined; here that fully connects the two triangles.
Try to pick one vertex per triangle. Any vertex from triangle 1 is an $x$ -vertex; any from triangle 2 is a $\neg x$ -vertex; they are always adjacent. So we cannot pick both. Why this step? Size-2 IS needs one from each triangle, but every such pair is an edge — impossible.

Verify: Max independent set here has size $1$ , which is $< k = 2$ . By the reduction's guarantee ( $ϕ$ satisfiable $⟺$ IS of size $m$ exists), no size-2 IS ⇒ $ϕ$ unsatisfiable — and indeed $(x) \land (\neg x)$ is unsatisfiable. The two "NO"s agree. ✔

Worked example Ex 6 — (C6) SAT

$\to$ 3-SAT clause splitting, all clause lengths Statement. Convert to 3-SAT: a long clause $C = (a \lor b \lor c \lor d)$ , a 2-literal clause $(e \lor f)$ , and a unit clause $(g)$ .

Forecast: the long clause needs helper variables; the short ones need padding. How many helpers for the 4-literal clause?

Long clause (4 literals) → split with one fresh variable $y$ : $C ⟶ (a \lor b \lor y) \land (\neg y \lor c \lor d) .$ Why this step? A $k$ -literal clause needs $k - 3$ fresh variables. Here $4 - 3 = 1$ . The chain of $y$ 's can be satisfied internally only if some original literal is true — so satisfiability is preserved.
2-literal clause → pad by repeating a literal: $(e \lor f) \to (e \lor f \lor f)$ . Why this step? Repetition adds no new meaning ( $f \lor f = f$ ) but hits the required length 3. (Padding with a fresh $z$ and its negation across two clauses also works.)
Unit clause → pad twice: $(g) \to (g \lor g \lor g)$ . Why this step? Same padding trick; keeps exactly the constraint " $g$ true".

Verify — the split preserves satisfiability. Check the 4-literal case by cases:

If some of $a, b, c, d$ is TRUE, we can choose $y$ to satisfy both new clauses. E.g. if $c$ or $d$ true, set $y = T$ (first clause needs $y$ , second satisfied by $c / d$ ); if $a$ or $b$ true, set $y = F$ .
If all of $a, b, c, d$ are FALSE: first clause needs $y = T$ , second needs $\neg y = T$ i.e. $y = F$ — contradiction, so unsatisfiable, exactly like the original all-false $C$ .

This matches " $C$ true $⟺$ split is satisfiable" ✔, and the count $k - 3$ helpers keeps the whole thing polynomial. Hence 3-SAT is NP-complete. ✔

Worked example Ex 7 — (C7) The direction trap

Statement. A student wants to prove that Vertex Cover is NP-hard. They write: "I'll give a poly-time map from Vertex Cover to SAT." Is their proof strategy correct? Fix it if not.

Forecast: recall the slogan "reduce FROM known-hard TO your new problem." Which side is Vertex Cover on?

Identify what "Vertex Cover $\leq_{p}$ SAT" proves. It shows Vertex Cover is no harder than SAT — i.e. it places Vertex Cover in NP-ish territory. Why this step? By the meaning of $A \leq_{p} B$ , the target $B$ is the harder side. Here $B =$ SAT, so this only says "SAT is at least as hard as Vertex Cover" — the wrong conclusion for a hardness proof.
State the correct direction. To prove Vertex Cover NP-hard, reduce a known NP-complete problem INTO it, e.g. Independent Set $\leq_{p}$ Vertex Cover (or 3-SAT $\leq_{p}$ Vertex Cover). Why this step? Then "everything $\leq_{p}$ Independent Set" plus transitivity gives "everything $\leq_{p}$ Vertex Cover".
Also show membership. Separately confirm Vertex Cover $\in$ NP (a cover of size $k$ is a poly-time-checkable certificate). NP-hard + in NP = NP-complete.

Verify: Consistency with the parent's mistake box — "To prove B hard, reduce a known-hard A TO B." The student had it backwards; the fixed direction is $IS \leq_{p} VC$ , which we actually build in Ex 8. ✔

Worked example Ex 8 — (C8) Chaining by transitivity: 3-SAT

$\to$ IS $\to$ Vertex Cover Statement. Using Ex 4's Independent-Set graph $G$ (with $n = 6$ vertices), turn the "IS of size $k$ " question into a "Vertex Cover of size $n - k$ " question, and confirm the numbers.

Forecast: there is a beautiful complement fact linking independent sets and vertex covers. If IS target is $k = 2$ and $n = 6$ , what is the VC target?

The complement fact. In any graph, $S$ is an independent set $⟺$ its complement $V ∖ S$ is a vertex cover. Why this step? If no edge lies inside $S$ (independent), then every edge has at least one endpoint outside $S$ — that outside set covers all edges (that is a cover), and vice versa.
Translate the target. "IS of size $\geq k$ " $⟺$ "VC of size $\leq n - k$ ". With $n = 6, k = 2$ : VC target $= 6 - 2 = 4$ . Why this step? $\leq_{p}$ is transitive, so 3-SAT $\leq_{p}$ IS and IS $\leq_{p}$ VC chain into 3-SAT $\leq_{p}$ VC — hardness flows all the way to Vertex Cover.
Sanity-map one solution. The IS ${x_{3}^{(1)}, x_{3}^{(2)}}$ from Ex 4 (size 2) ⇒ its complement, the other 4 vertices, is a vertex cover of size 4.

Verify: $n - k = 6 - 2 = 4$ ✔. Every edge of $G$ must touch the complement: since the two chosen vertices are non-adjacent, no edge lives inside the IS, so all edges are covered by the remaining 4. Transitivity gives 3-SAT $\leq_{p}$ VC, so Vertex Cover is NP-hard. ✔

Worked example Ex 9 — (C9) Real-world word problem: course scheduling

Statement. A department must offer 3 courses in 2 time-slots. Constraints: (i) courses A and B share students → different slots; (ii) course C must be in slot 1 (only room available). Can it be scheduled? Model as SAT and solve.

Forecast: two slots = one bit each. Guess: schedulable or not?

Encode with Boolean variables. Let $a = T$ mean "A in slot 1" (else slot 2), likewise $b, c$ . Why this step? With only 2 slots, one bit per course captures the whole schedule — the same "physical config ↔ truth assignment" idea as the Cook tableau, in miniature.
Encode "A and B different slots". Different means $a \neq = b$ , i.e. $(a \lor b) \land (\neg a \lor \neg b)$ . Why this step? XOR-as-two-clauses: "at least one in slot 1" AND "not both in slot 1".
Encode "C in slot 1". Unit clause $(c)$ . Why this step? A hard requirement is a one-literal clause forcing $c = T$ .
Solve $ϕ = (a \lor b) \land (\neg a \lor \neg b) \land (c)$ . Force $c = T$ . Pick $a = T, b = F$ : clause 1 $= T$ , clause 2 $= (F \lor T) = T$ . Why this step? Resolve the forced unit first, then satisfy the XOR.

Verify: Assignment $a = T, b = F, c = T$ ⇒ A in slot 1, B in slot 2 (different ✔), C in slot 1 (✔). $ϕ$ evaluates TRUE. Schedulable. This is a genuine (tiny) instance of the SAT that Cook's theorem crowns as NP-complete. ✔

Recall Quick self-test

Direction of a hardness reduction ::: reduce FROM a known NP-complete problem TO your new problem ( $A \leq_{p} B$ proves $B$ hard) Satisfiability of the empty formula ::: always TRUE (empty AND = identity of AND) Satisfiability of a formula containing the empty clause ::: always FALSE (empty OR = identity of OR) In the 3-SAT $\to$ IS reduction, what does a triangle enforce? ::: pick at most one literal per clause IS of size $k$ corresponds to a Vertex Cover of size ::: $n - k$ Helpers needed to split a $k$ -literal clause into 3-SAT ::: $k - 3$ fresh variables