Reductions and NP-Completeness — Mathematics Knowledge System

Overview

A reduction transforms instances of one problem into instances of another so that solving the second problem also solves the first. Reductions are the connective tissue of complexity theory: they let us compare the difficulty of different problems precisely, without solving either one directly. A problem is NP-hard if every problem in NP can be reduced to it in polynomial time — informally, it is 'at least as hard' as anything in NP — and NP-complete if it is additionally itself in NP. The 1971 Cook-Levin theorem showed the Boolean satisfiability problem (SAT) is NP-complete, and thousands of practical problems (scheduling, routing, packing) have since been shown NP-complete via chains of polynomial-time reductions from SAT, revealing they are all, in a precise sense, equally hard.

Intuition

A reduction is like translating one puzzle into another: if you can always rewrite any instance of puzzle A as an instance of puzzle B (quickly), then any method for solving B also solves A — you just translate first. If it turns out EVERY puzzle in a huge, important class (NP) can be translated into puzzle B this way, then B is at least as hard as the hardest thing in that entire class; solve B efficiently and you've secretly solved all of them efficiently. NP-complete problems are exactly the 'universal translators' of NP: SAT, and thousands of problems reachable from it by a chain of reductions, all rise and fall together — either all of them have efficient algorithms, or none of them do.

Formal Definition

Definition

A polynomial-time (Karp) reduction from language A to language B, and the resulting definitions of NP-hardness and NP-completeness:

A \le_p B \iff \exists \text{ polynomial-time computable } f \text{ such that } \forall x,\ x \in A \iff f(x) \in B

Polynomial-time (Karp) reduction

B \text{ is NP-hard} \iff \forall A \in NP,\ A \le_p B

NP-hardness

B \text{ is NP-complete} \iff B \in NP \text{ and } B \text{ is NP-hard}

NP-completeness

Notation

Notation	Meaning
$\le_p$	'Polynomial-time reducible to' — A ≤ₚ B means A is no harder than B, up to a polynomial-time translation
$f$	The polynomial-time computable reduction function transforming instances of A into instances of B

Theorems

Theorem 1: Cook-Levin theorem

\text{SAT (Boolean satisfiability) is NP-complete.}

Theorem 2: Transitivity of reductions

\text{If } A \le_p B \text{ and } B \le_p C, \text{ then } A \le_p C.

Theorem 3: Consequence for P vs NP

\text{If any single NP-complete problem is solvable in polynomial time, then } P = NP; \text{ conversely if any NP-complete problem provably requires super-polynomial time, then } P \ne NP.

Applications

To prove a newly encountered problem is NP-hard, engineers reduce a KNOWN NP-complete problem (like 3-SAT or vertex cover) TO it in polynomial time — this is the standard recipe used throughout algorithms research and interviews.

Worked Examples

Given a 3-SAT formula with m clauses, build a graph with one vertex per literal occurrence, grouped into m clause-groups of up to 3 vertices each.
$\varphi = C_1 \wedge C_2 \wedge \cdots \wedge C_m$
Connect two vertices with an edge exactly when they're in different clause-groups and are not negations of each other (i.e. they can be simultaneously true).
$\text{edge}(u,v) \iff \text{group}(u) \ne \text{group}(v) \text{ and } u \ne \lnot v$
Show φ is satisfiable if and only if this graph has a clique of size m (one consistent, mutually-compatible literal chosen from each clause-group).
$\varphi \text{ satisfiable} \iff \text{graph has a } k\text{-clique with } k=m$

Answer: This construction runs in polynomial time and correctly preserves satisfiability, so 3-SAT ≤ₚ CLIQUE; since 3-SAT is NP-complete, this shows CLIQUE is NP-hard (and it's easily seen to be in NP, so it's NP-complete).

Practice Problems

Difficulty 7/10

Why does proving A ≤ₚ B show that B is 'at least as hard as' A, rather than the other way around?

Difficulty 7/10

A company's logistics team encounters a new bin-packing variant and, after failing to find an efficient algorithm for months, proves that the classical NP-complete SUBSET-SUM problem reduces to it in polynomial time. What does this tell them, and what should they do next?

Difficulty 6/10

To prove a new problem X is NP-hard, the standard technique is to:

Reduce X to a known NP-complete problemReduce a known NP-complete problem to XShow X can be solved in exponential timeShow X is in P

Difficulty 6/10

What is the difference between a problem being NP-hard and being NP-complete?

Common Mistakes

Common Mistake

Reducing a problem TO a known-hard problem (in the wrong direction) to try to prove NP-hardness.

To prove X is NP-hard, you must reduce a KNOWN NP-hard/NP-complete problem TO X, not reduce X to something else. Reducing X to an easy problem tells you nothing about X's hardness.

Common Mistake

Believing NP-hard and NP-complete are synonyms.

NP-complete requires membership in NP as well as NP-hardness; a problem can be NP-hard without being in NP at all (e.g. it could be undecidable, and thus NP-hard but not NP-complete).

Common Mistake

Thinking that proving a problem NP-complete means it can never be solved for any practical instance.

NP-completeness is a WORST-CASE statement. Many NP-complete problems have algorithms (exact solvers, heuristics, approximations) that work very well on real-world instance distributions, even though some pathological instances would take exponential time.

Quiz

Historical Background

Stephen Cook's 1971 paper 'The Complexity of Theorem-Proving Procedures' proved that Boolean satisfiability (SAT) is NP-complete — the first problem shown to have this property, establishing that a solution to SAT in polynomial time would imply P = NP. Leonid Levin independently discovered an equivalent result in the Soviet Union around the same time, so the theorem is now called the Cook-Levin theorem. Richard Karp's 1972 paper 'Reducibility Among Combinatorial Problems' then used polynomial-time reductions FROM SAT to show 21 other well-known problems (including vertex cover, clique, and the traveling salesman decision problem) are also NP-complete, launching the now-enormous catalogue of NP-complete problems.

1971
Stephen Cook proves SAT is NP-complete (the Cook-Levin theorem)
Stephen Cook
1971
Leonid Levin independently proves an equivalent NP-completeness result
Leonid Levin
1972
Richard Karp reduces SAT to 21 further problems, proving them all NP-complete
Richard Karp

Summary

A polynomial-time reduction A ≤ₚ B shows B is at least as hard as A (an efficient B-algorithm yields an efficient A-algorithm).
NP-hard: every problem in NP reduces to it. NP-complete: NP-hard AND in NP.
The Cook-Levin theorem (1971) proved SAT is NP-complete; Karp (1972) then reduced SAT to 21 more problems.
To prove a new problem NP-hard, reduce a KNOWN NP-complete problem TO it — never the reverse direction.
NP-completeness is a worst-case guarantee; heuristics and approximations remain practical for real-world instances.

References

WebsiteWikipedia — NP-completeness
WebsiteWikipedia — Karp's 21 NP-complete problems