In computability theory and computational complexity theory, a many-one reduction (also called mapping reduction) is a reduction which converts instances of one decision problem (whether an instance is in ) to another decision problem (whether an instance is in ) using an effective function. The reduced instance is in the language if and only if the initial instance is in its language . Thus if we can decide whether instances are in the language , we can decide whether 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. It is said that reduces to if, in layman's terms is at least as hard to solve as . This means that any algorithm that solves 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. 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. This means that if we want to show that problem can be reduced to problem , we can use our solution for only once in our solution for , 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. Later Norman Shapiro used the same concept in 1956 under the name strong reducibility.
Definitions
Formal languages
Suppose and are formal languages over the alphabets and , respectively. A many-one reduction from to is a total computable function that has the property that each word is in if and only if is in .
If such a function exists, one says that is many-one reducible or m-reducible to and writes
Subsets of natural numbers
Given two sets one says is many-one reducible to and writes
if there exists a total computable function with iff .
If the many-one reduction is injective, one speaks of a one-one reduction and writes .
If the many-one reduction is surjective, one says is recursively isomorphic to and writesp.324
Many-one equivalence
If both and , one says is many-one equivalent or m-equivalent to and writes
Many-one completeness (m-completeness)
A set is called many-one complete, or simply m-complete, iff is recursively enumerable and every recursively enumerable set is m-reducible to .
Degrees
The relation indeed is an equivalence, its equivalence classes are called m-degrees and form a poset with the order induced by .p.257
Some properties of the m-degrees, some of which differ from analogous properties of Turing degrees:pp.555--581 There is a well-defined jump operator on the m-degrees. The only m-degree with jump 0m′ is 0m. There are m-degrees where there does not exist where . Every countable linear order with a least element embeds into . The first order theory of is isomorphic to the theory of second-order arithmetic.
There is a characterization of as the unique poset satisfying several explicit properties of its ideals, a similar characterization has eluded the Turing degrees.pp.574--575
Myhill's isomorphism theorem can be stated as follows: "For all sets of natural numbers, ." As a corollary, and have the same equivalence classes.p.325 The equivalences classes of are called the 1-degrees.
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 or 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 and and an algorithm N which solves instances of , we can use a many-one reduction from to to solve instances of 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