3.1 The standard recipe (write it at the top of every answer)

To prove problem B NP-complete:

1. B ∈ NP. Name the certificate; argue the verifier is polynomial. (One sentence — but worth marks, and forgetting it is the #1 exam error.)
2. Pick a known NP-complete source A and build f with A ≤ₚ B.
3. f is polynomial-time computable. (Usually obvious — say it anyway.)
4. Correctness both ways: x ∈ A ⟹ f(x) ∈ B, and f(x) ∈ B ⟹ x ∈ A. The second direction is where wrong proofs die: you must show every solution of the constructed instance decodes to a solution of the original, including "cheating" solutions you didn't intend.

Direction check (the eternal trap): reduce FROM the known hard problem TO yours. A ≤ₚ B makes B hard; B ≤ₚ A says nothing about B.

3.2 Choosing the source problem — pattern matching

The closer the source's shape to B, the smaller the gadget work.

3.3 Technique 1 — restriction (the 30-second proof)

Show B contains a known NP-complete problem as a special case; the reduction is the identity (or near-identity) map.

Examples: TSP-decision restricted to edge weights {1, 2} is HAM-CYCLE (weight-1 edges = graph edges; tour of cost n ⟺ Hamiltonian cycle). SET-COVER with every set of size 2 is VERTEX-COVER (now: EDGE-COVER... careful — check the special case really is the known problem!). Always try restriction first.

3.4 Technique 2 — local replacement

Transform instance pieces one-for-one through a uniform local rule; no global coordination. The SAT → 3-SAT clause-splitting (previous lesson) is the canonical case: each clause rewritten independently by width.

3.5 Technique 3 — gadget construction (component design)

The heavy machinery for cross-domain reductions. From a 3-SAT formula you build:

• Choice/variable gadgets — a structure with exactly two "states" encoding true/false (in 3-COLOURING: a pair of vertices joined to a reference triangle; in HAM-CYCLE: a row traversable left-to-right or right-to-left).
• Constraint/clause gadgets — a structure satisfiable only when at least one incoming literal is in its "true" state (an OR-gate built from edges).
• Consistency wiring — edges forcing all occurrences of a variable to agree (and in number problems, digit columns forcing each variable picked exactly once — the SUBSET-SUM table: one digit column per variable, one per clause, slack rows to top clause columns up to the target).

Worked sketch — 3-SAT ≤ₚ 3-COLOURING:

1. Palette triangle T–F–B (three mutually joined vertices fix the three colour roles).
2. Per variable x: vertices x and ¬x, joined to each other and to B → one gets colour T, the other F. (choice gadget)
3. Per clause (ℓ₁ ∨ ℓ₂ ∨ ℓ₃): an OR-gadget of ~6 vertices wired to ℓ₁, ℓ₂, ℓ₃ and to the palette, 3-colourable iff at least one ℓᵢ has colour T. (constraint gadget)
4. Both directions: a satisfying assignment extends to a 3-colouring gadget-by-gadget; conversely any 3-colouring reads off a consistent satisfying assignment from the variable vertices. ∎

3.6 Worked exam answer — DOUBLE-SAT

DOUBLE-SAT = { φ : φ has at least two satisfying assignments }. Prove NP-completeness.

1. ∈ NP: certificate = two distinct assignments; verify both, compare. ✓
2. SAT ≤ₚ DOUBLE-SAT: map φ(x₁...xₙ) ↦ φ' = φ ∧ (y ∨ ¬y) with fresh variable y.
3. f adds one clause — linear time. ✓
4. φ satisfiable by A ⟹ A extended with y=T and with y=F gives two models of φ' ⟹ φ' ∈ DOUBLE-SAT. Conversely φ' has ≥ 2 models ⟹ ≥ 1 ⟹ restricting any model to x₁...xₙ satisfies φ. ∎

Four steps, each named, both directions argued — this template scores full marks.

3.7 Pitfall checklist

• ❌ Reduced the wrong direction.
• ❌ Forgot B ∈ NP (then you've shown NP-hard only — state which you proved!).
• ❌ Proved only one direction of the iff — especially missing that unintended solutions of f(x) still decode correctly.
• ❌ Reduction takes exponential time (e.g. "enumerate all assignments and...").
• ❌ Certificate that isn't polynomial-size.
• ⚠ If numbers appear, note weak vs strong NP-completeness (pseudo-polynomial DP may exist — SUBSET-SUM yes, TSP no).

3.8 A second full worked answer — PARTITION from SUBSET-SUM

PARTITION = { ⟨a₁...aₙ⟩ : the numbers split into two halves of equal sum }. Prove it NP-complete.

1. ∈ NP: certificate = one side S of the split; verify ΣS = (Σ all)/2 in one pass. ✓
2. Source: SUBSET-SUM — instance a₁...aₙ, target T; write W = Σaᵢ (assume 0 ≤ T ≤ W, else answer NO directly).
3. Construction f: output the n + 2 numbers a₁, ..., aₙ, W + T, 2W − T. The new total is 4W, so each side of an equal split must sum to 2W. Polynomial: one addition and two new numbers. ✓
4. (⟹) If some S sums to T: put S together with (2W − T) — that side totals T + (2W − T) = 2W ✓ — and the rest with (W + T): (W − T) + (W + T) = 2W ✓.

(⟸) In any equal split the two padding numbers must be on different sides, since together they total (W+T) + (2W−T) = 3W > 2W — more than one side's whole budget. The side containing (2W − T) therefore has original numbers summing to 2W − (2W − T) = T — a subset-sum witness. ∎

Note the structure of step 4(⟸): we forced the gadget numbers apart with a size argument, then decoded the arbitrary solution back to the source problem. That decoding move is what separates correct proofs from hopeful ones.

3.9 How marks are typically distributed (calibrate your effort)

Spending twenty minutes perfecting the gadget while skipping "∈ NP" donates two free marks back to the examiner. Write the skeleton first, decorate second.

3.10 Practice ladder (attempt in this order)

1. Restriction warm-ups: TSP(decision) from HAM-CYCLE; KNAPSACK(decision) from SUBSET-SUM (set weights = values = aᵢ, W = V = T).
2. One-liners: IND-SET from CLIQUE (complement graph); VERTEX-COVER from IND-SET (V∖S); DOUBLE-SAT from SAT (§3.6).
3. Local replacement: 3-SAT from SAT (the clause-width table).
4. Arithmetic gadgets: PARTITION from SUBSET-SUM (§3.8); then SUBSET-SUM from 3-SAT (the digit table).
5. Full gadget constructions: CLIQUE from 3-SAT; 3-COLOURING from 3-SAT (palette + OR-gadget, §3.5).

If you can write levels 1–4 from a blank page and sketch level 5, the reduction question on the paper is banked.

Self-check

1. Recite the four-step recipe without notes.
2. In DOUBLE-SAT's proof, why must y be a fresh variable?
3. In the PARTITION proof, why exactly can the two padding numbers never share a side?
4. A friend "proves" X NP-hard by reducing X to 3-SAT. What did they actually establish, and what is the fix?
5. Which technique — restriction, local replacement, or gadget construction — does each of these use: TSP from HAM-CYCLE; 3-SAT from SAT; 3-COLOURING from 3-SAT?