Editing Reduction (complexity) (section)

== Types and applications of reductions ==
As described in the example above, there are two main types of reductions used in computational complexity, the [[many-one reduction]] and the [[Turing reduction]]. Many-one reductions map ''instances'' of one problem to ''instances'' of another; Turing reductions ''compute'' the solution to one problem, assuming the other problem is easy to solve. The many-one reduction is a stronger type of Turing reduction, and is more effective at separating problems into distinct complexity classes. However, the increased restrictions on many-one reductions make them more difficult to find.

A problem is [[complete (complexity)|complete]] for a complexity class if every problem in the class reduces to that problem, and it is also in the class itself. In this sense the problem represents the class, since any solution to it can, in combination with the reductions, be used to solve every problem in the class.

However, in order to be useful, reductions must be ''easy''. For example, it's quite possible to reduce a difficult-to-solve [[NP-complete]] problem like the [[boolean satisfiability problem]] to a trivial problem, like determining if a number equals zero, by having the reduction machine solve the problem in exponential time and output zero only if there is a solution. However, this does not achieve much, because even though we can solve the new problem, performing the reduction is just as hard as solving the old problem. Likewise, a reduction computing a [[computable function|noncomputable function]] can reduce an [[undecidable problem]] to a decidable one. As Michael Sipser points out in ''Introduction to the Theory of Computation'': "The reduction must be easy, relative to the complexity of typical problems in the class [...] If the reduction itself were difficult to compute, an easy solution to the complete problem wouldn't necessarily yield an easy solution to the problems reducing to it."

Therefore, the appropriate notion of reduction depends on the complexity class being studied. When studying the complexity class [[NP (complexity)|NP]] and harder classes such as the [[polynomial hierarchy]], [[polynomial-time reduction]]s are used. When studying classes within P such as [[NC (complexity)|NC]] and [[NL (complexity)|NL]], [[log-space reduction]]s are used. Reductions are also used in [[computability theory]] to show whether problems are or are not solvable by machines at all; in this case, reductions are restricted only to [[computable function]]s.

In case of optimization (maximization or minimization) problems, we often think in terms of [[approximation-preserving reduction]]. Suppose we have two optimization problems such that instances of one problem can be mapped onto instances of the other, in a way that nearly optimal solutions to instances of the latter problem can be transformed back to yield nearly optimal solutions to the former. This way, if we have an optimization algorithm (or [[approximation algorithm]]) that finds near-optimal (or optimal) solutions to instances of problem B, and an efficient approximation-preserving reduction from problem A to problem B, by composition we obtain an optimization algorithm that yields near-optimal solutions to instances of problem A. Approximation-preserving reductions are often used to prove [[hardness of approximation]] results: if some optimization problem A is hard to approximate (under some complexity assumption) within a factor better than α for some α, and there is a β-approximation-preserving reduction from problem A to problem B, we can conclude that problem B is hard to approximate within factor α/β.