3.1 The idea: solving A by translating it into B

A polynomial-time (many-one/Karp) reduction from A to B, written A ≤ₚ B, is a function f computable in polynomial time such that for every input x:

x ∈ A ⟺ f(x) ∈ B

So a solver for B becomes a solver for A: translate the instance with f, ask B.

3.2 Reading "≤ₚ" correctly — the direction trap

A ≤ₚ B means "A is no harder than B" (B is at least as hard as A). The two consequences, used in opposite directions:

The classic exam error: to prove a new problem NEW is NP-hard you must reduce FROM a known NP-hard problem TO NEW (KNOWN ≤ₚ NEW) — never the other way. Reducing NEW to SAT only shows NEW ∈ NP-easy territory, proving nothing about hardness.

Key properties: ≤ₚ is transitive (A ≤ₚ B and B ≤ₚ C ⟹ A ≤ₚ C) — this is what lets hardness propagate along chains of reductions — and both P and NP are closed downward under ≤ₚ.

3.3 A complete worked reduction: 3-SAT ≤ₚ CLIQUE

3-SAT: given a CNF formula with exactly 3 literals per clause, is it satisfiable? CLIQUE: given graph G and k, does G contain k mutually adjacent vertices?

Construction f. For a formula φ with m clauses:

1. Create one vertex per literal occurrence (3m vertices, grouped into m clause-triples).
2. Join two vertices by an edge iff they are in different clauses AND are not contradictory (not x and ¬x).
3. Set k = m.

Correctness (⟹). If φ is satisfiable, pick one true literal from each clause — these m vertices lie in different clauses and can't be contradictory (they're all true), so all pairs are joined: a k-clique.

Correctness (⟸). A k-clique with k = m must take exactly one vertex from each clause-triple (same-clause vertices are non-adjacent). Set those literals true — no contradiction is possible (contradictory vertices are non-adjacent), and every clause has a true literal: φ is satisfiable. ∎

Polynomiality. The graph has 3m vertices and ≤ 9m² candidate edges — construction is O(m²). ∎

Example. φ = (x ∨ y ∨ ¬z) ∧ (¬x ∨ y ∨ z): 6 vertices; the assignment y = true picks vertex y in both triples — adjacent, a 2-clique, k = m = 2 ✓.

3.4 A second flavour: SUBSET-SUM is number-based

Reductions also target numeric problems. From 3-SAT one builds, for each variable and clause, carefully positioned decimal digits so that a subset summing to a target exists iff the formula is satisfiable — showing hardness can hide inside plain arithmetic. (You'll see gadget tables like this in Unit 3.)

3.5 Turing reductions (for contrast)

A Turing/Cook reduction lets you call a B-oracle many times and post-process. Karp reductions are the standard for defining NP-completeness because they're more fine-grained; Cook reductions are what you actually write in practice ("binary-search the threshold k" turns an optimisation problem into many decision queries).

3.6 Reductions you should be able to sketch by Unit 3

SAT ≤ₚ 3-SAT ≤ₚ CLIQUE ≤ₚ VERTEX-COVER
            └────≤ₚ──── SUBSET-SUM
            └────≤ₚ──── HAM-CYCLE ≤ₚ TSP(decision)

Each arrow is one gadget construction; together with Cook–Levin they put thousands of problems on the summit. Memorise the map now — Unit 3 fills in the proofs.

3.7 The two lemmas, proved (write once, reuse forever)

Lemma A (easiness travels down). If A ≤ₚ B and B ∈ P, then A ∈ P. Proof. Let f run in time O(nᵏ) and let B's decider run in time O(nˡ). On input x: compute f(x) — time O(|x|ᵏ), and crucially |f(x)| ≤ c·|x|ᵏ (a machine cannot write more output than it has steps). Run B's decider on f(x) — time O((c|x|ᵏ)ˡ) = O(|x|ᵏˡ). Total: polynomial. Correctness is immediate from x ∈ A ⟺ f(x) ∈ B. ∎ The size remark is the marks-bearing subtlety: it is why the composed bound stays polynomial.

Lemma B (transitivity). If A ≤ₚ B via f and B ≤ₚ C via g, then A ≤ₚ C via g∘f. Proof. x ∈ A ⟺ f(x) ∈ B ⟺ g(f(x)) ∈ C; computing g(f(x)) is a polynomial of a polynomial — polynomial, by the same size argument. ∎

3.8 A second worked one-liner: IND-SET ≤ₚ VERTEX-COVER

Claim: S is an independent set of G = (V, E) ⟺ V∖S is a vertex cover of G. Proof: S independent ⟺ no edge has both endpoints in S ⟺ every edge has at least one endpoint in V∖S ⟺ V∖S is a cover. ∎ Reduction: f(⟨G, k⟩) = ⟨G, n−k⟩. Trivially polynomial; correctness is the claim with |S| = k. This is the smallest complete reduction in the course — when an exam asks "define reduction and give an example", this one fits in five lines.

3.9 What a reduction is NOT (common misconceptions)

• It is not an algorithm for A by itself — it needs B's solver attached at the far end.
• It may not call B's solver during f (that would be a Turing reduction); a Karp reduction only builds an instance.
• It need not be reversible, injective or surjective — only the iff matters.
• It does not in general preserve the number of solutions (DOUBLE-SAT in Unit 3 exploits exactly this); reductions that do are called parsimonious — a finer notion you only need to name-drop.

Exam pointer

"Define polynomial-time reduction and explain its role in NP-completeness" (5–6 marks): the definition with the iff, the pipeline diagram, Lemma A and its contrapositive ("if A is hard, B is hard"), the direction warning, and transitivity. If an example is demanded, use IND-SET ↔ VERTEX-COVER (§3.8) for speed or 3-SAT → CLIQUE (§3.3) for depth.

Self-check

1. A ≤ₚ B and A ∉ P: what (if anything) follows about B?
2. A ≤ₚ B and B ∈ NP: does A ∈ NP follow? (Yes — certificate for x is the certificate of f(x); NP is closed downward under ≤ₚ.)
3. Why must f's output be polynomially bounded in size, and what guarantees it?
4. In the 3-SAT → CLIQUE construction, why are vertices of the same clause never joined by an edge?
5. Using only ≤ₚ arrows, write the chain showing TSP(decision) is at least as hard as 3-SAT.