Reductions

A reduction transforms one problem into another so that solving the second solves the first, transferring difficulty between them.

The core idea

A reduction from problem A to problem B is a procedure that converts any instance of A into an instance of B, preserving the answer. If you can solve B, you can solve A by translating and solving. This lets us compare the difficulty of problems: A is "no harder than" B.

Polynomial-time many-one reductions

Kronos motion — materials first

The standard reduction in complexity theory is the polynomial-time many-one reduction: a polynomial-time function f such that A accepts x if and only if B accepts f(x). The transformation must be efficient, so it cannot smuggle in the hard work itself.

How hardness transfers

Reductions run in two directions of argument. To show B is hard, reduce a known-hard problem A to B: if B were easy, A would be too. To show B is easy, reduce it to a known-easy problem. This is how NP-completeness proofs propagate difficulty from one problem to thousands.

A reduces to B and B is easy implies A is easy
A reduces to B and A is hard implies B is hard
Reductions compose: A to B and B to C gives A to C

A worked reduction

To show independent set is NP-hard, reduce from clique. A graph has a clique of size k exactly when its complement graph has an independent set of size k. Building the complement graph is polynomial, so a fast independent-set solver would give a fast clique solver. Since clique is NP-hard, so is independent set.

Turing versus many-one

A many-one reduction makes a single call to the solver for B and returns its answer. A more general Turing reduction may call B many times and process results. Many-one reductions are stricter and are the right tool for defining completeness, because they preserve class membership tightly.

Why reductions are central

Reductions are the connective tissue of complexity theory. They organize problems into classes, prove hardness, and reveal that superficially different tasks share the same computational core. Almost every major result, from Cook-Levin onward, is built on a carefully constructed reduction.