Reducibility

Reducibility is the fundamental relation in computational complexity and computability theory: problem A reduces to problem B if an algorithm for B can solve A. If A reduces to B, then B is at least as hard as A — any efficient or computable solution to B transfers to A. Reductions formalize the notion of 'at most as hard as.'

Many-one reductions (or polynomial-time reductions in complexity theory) transform instances: a reduction from A to B is a function f computable in polynomial time such that x ∈ A iff f(x) ∈ B. Turing reductions are more powerful: they allow multiple oracle calls to B while solving A.

Reductions are the primary tool for proving NP-completeness and for establishing the boundaries between complexity classes. Cook's proof that SAT is NP-complete was a many-one reduction from every NP problem to SAT. When a problem reduces to one already known easy, it is easy; when it reduces from one already known hard, it is hard. The structure of the complexity landscape is a lattice of reductions.