In computability and complexity, finding mappings between problems that allow solving one problem using a solution of another one. For reduction in programming language theory (e.g. beta-reduction), see [lambda-calculus] or [term-rewriting].
Reduction in computability and in computational complexity is the process of solving one problem using a solution of another one.
Popular examples include:
- Proving undecidability of $P$ by reducing the halting (or any undecidable) problem $\mathrm{HP}$ to $P$. This entails finding a computable function $f$ with $\mathrm{HP}(I) = \mathrm{true} \Longleftrightarrow P(f(I)) = \mathrm{true}$ to use in a proof by contradiction.
- Proving that a (decision) problem $P$ is np-hard by reducing an NP-hard problem $P'$ (for instance 3-sat) to $P$, i.e. finding a function $f$ with polynomial runtime and $P'(I) = \mathrm{true} \Longleftrightarrow P(f(I)) = \mathrm{true}$.
- Many optimisation problems can be solved by reducing them to linear-programming, a well studied class of problems, i.e. you solve problem $P$ by formulating a linear program $\mathrm{LP}_P$ so that $\operatorname{opt}(P) = \operatorname{opt}(\mathrm{LP}_P)$ and solve $\mathrm{LP}_P$ with one of the canonical algorithms. network-flow-problems are classical examples.
As you can see, the basic scheme is always the same.
Note that you can have several layers of reduction. For instance in the NP-hardness proof, we reduce the problem of proving that $P$ is NP-hard to the problem of proving that $P'$ is NP-hard (which we have previously solved). We do this by reducing $P'$ to $P$. Note that the reductions have opposite directions; therefore you have to be very clear about which reduction you are talking about.
Two types of "reduction"
In theory of computability, there are two main types of reductions. The more powerful one is Turing reduction. The other more restricted one is called many-one reduction. Depending on the situation, each of these may be more useful than the other.
Other meanings of “reduction”
- For beta-reduction, eta-reduction and other rules of programming calculi, use tags corresponding to the calculus, e.g. lambda-calculus.
- For the general concept of reduction rules and reduction strategies in term rewriting, see term-rewriting.
