Editing Many-one reduction (section)

== Many-one reductions with resource limitations ==

Many-one reductions are often subjected to resource restrictions, for example that the reduction function is computable in polynomial time, logarithmic space, by <math>AC_0</math> or <math>NC_0</math> circuits, or polylogarithmic projections where each subsequent reduction notion is weaker than the prior; see [[polynomial-time reduction]] and [[log-space reduction]] for details.

Given decision problems <math>A</math> and <math>B</math> and an [[algorithm]] ''N'' that solves instances of <math>B</math>, we can use a many-one reduction from <math>A</math> to <math>B</math> to solve instances of <math>A</math> in:
* the time needed for ''N'' plus the time needed for the reduction
* the maximum of the space needed for ''N'' and the space needed for the reduction

We say that a class '''C''' of languages (or a subset of the [[power set]] of the natural numbers) is ''closed under many-one reducibility'' if there exists no reduction from a language outside '''C''' to a language in '''C'''. If a class is closed under many-one reducibility, then many-one reduction can be used to show that a problem is in '''C''' by reducing it to a problem in '''C'''. Many-one reductions are valuable because most well-studied complexity classes are closed under some type of many-one reducibility, including [[P (complexity)|P]], [[NP (complexity)|NP]], [[L (complexity)|L]], [[NL (complexity)|NL]], [[co-NP]], [[PSPACE]], [[EXP]], and many others. It is known for example that the first four listed are closed up to the very weak reduction notion of polylogarithmic time projections.  These classes are not closed under arbitrary many-one reductions, however.