In computability theory and computational complexity theory, a many-one reduction (also called mapping reduction[1]) is a reduction that converts instances of one decision problem (whether an instance is in
instances are in its language by applying the reduction and solving for
Thus, reductions can be used to measure the relative computational difficulty of two problems.
can also be used as part of a (otherwise relatively simple) program that solves
Many-one reductions are a special case and stronger form of Turing reductions.
[1] With many-one reductions, the oracle (that is, our solution for
) can be invoked only once at the end, and the answer cannot be modified.
, unlike in Turing reductions, where we can use our solution for
as many times as needed in order to solve the membership problem for the given instance of
Many-one reductions were first used by Emil Post in a paper published in 1944.
[2] Later Norman Shapiro used the same concept in 1956 under the name strong reducibility.
is many-one reducible or m-reducible to
and writes if there exists a total computable function
is injective, one speaks of a one-one reduction and writes
is many-one equivalent or m-equivalent to
is called many-one complete, or simply m-complete, iff
[4]p.257 Some properties of the m-degrees, some of which differ from analogous properties of Turing degrees:[4]pp.555--581 There is a characterization of
as the unique poset satisfying several explicit properties of its ideals, a similar characterization has eluded the Turing degrees.
[4]pp.574--575 Myhill's isomorphism theorem can be stated as follows: "For all sets
Many-one reductions are often subjected to resource restrictions, for example that the reduction function is computable in polynomial time, logarithmic space, by
circuits, or polylogarithmic projections where each subsequent reduction notion is weaker than the prior; see polynomial-time reduction and log-space reduction for details.
in: 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, NP, L, 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.
One may also ask about generalized cases of many-one reduction.
The resulting reducibility relation is denoted
, and its poset has been studied in a similar vein to that of the Turing degrees.
The e-degrees do admit some properties differing from those of the poset of Turing degrees, e.g. an embedding of the diamond graph into the degrees below
An instance x of problem A can be solved by applying this transformation to produce an instance y of problem B, giving y as the input to an algorithm for problem B, and returning its output.
Polynomial-time many-one reductions may also be known as polynomial transformations or Karp reductions, named after Richard Karp.