Reductions and NP-completeness
Introduced
Vocabulary
| English | Meaning |
|---|---|
| reduction/rɪˈdʌkʃn/ | A transformation relating the solution of one problem to the solution of another. |
| NP-completeness | The property of being in NP and at least as hard as every NP problem under polynomial-time reductions. |
One problem in another's clothes
- A reduction $A \le_p B$ is a polynomial translator turning $A$-instances into $B$-instances: a $B$-solver then solves $A$. NP-completeness = in NP + every NP problem reduces to it.
{exercise:uni-cs1006-reduction}
Practice
A reduction A to B gives —
Difficulty 1/5 · 100 coins + a small bonus on first completion today
The translator maps A-instances to B-instances: solving B solves A.
The two-step hardness proof
- To prove $B$ NP-hard: pick a known NP-complete $A$, build a polynomial translator $A \to B$. The difficulty flows INTO your problem — you reduce the known hard problem TO yours.
- The course chain: SAT $\to$ 3-SAT (clause splitting), 3-SAT $\to$ CLIQUE (the triangle gadget), CLIQUE $\to$ VERTEX-COVER (complement the graph).
{exercise:uni-cs1006-hardness}
Practice
To prove B NP-hard, reduce —
Difficulty 1/5 · 100 coins + a small bonus on first completion today
The difficulty flows into your problem: known-hard TO yours.
The direction is the content
- Clique-to-cover, concretely: $G$ = triangle ABC plus isolated D has a 3-clique; the complement's edges are exactly A–D, B–D, C–D, and {D} — size $n - k = 1$ — covers them all.
- Reducing YOUR problem to SAT proves nothing about hardness — the arrow points the easy way. And NP means verifiable in polynomial time; P sits inside NP.
{exercise:uni-cs1006-direction}
Practice
Encoding your problem as SAT proves —
Difficulty 1/5 · 100 coins + a small bonus on first completion today
The arrow points the easy way: your problem reduces TO SAT.