In computability theory and computational complexity theory, a many-one reduction (also called mapping reduction ) is a reduction that converts instances of one decision problem (whether an instance is in L_1) to another decision problem (whether an instance is in L_2) using a computable function. The reduced instance is in the language L_2 if and only if the initial instance is in its language L_1. Thus if we can decide whether L_2 instances are in the language L_2, we can decide whether L_1 instances are in its language by applying the reduction and solving for L_2. Thus, reductions can be used to measure the relative computational difficulty of two problems. It is said that L_1 reduces to L_2 if, in layman's terms L_2 is at least as hard to solve as L_1. This means that any algorithm that solves L_2 can also be used as part of a (otherwise relatively simple) program that solves L_1. Many-one reductions are a special case and stronger form of Turing reductions. With many-one reductions, the oracle (that is, our solution for L_2) can be invoked only once at the end, and the answer cannot be modified. This means that if we want to show that problem L_1 can be reduced to problem L_2, we can use our solution for L_2 only once in our solution for L_1, unlike in Turing reductions, where we can use our solution for L_2 as many times as needed in order to solve the membership problem for the given instance of L_1. 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 A and B are formal languages over the alphabets \Sigma and \Gamma, respectively. A many-one reduction from A to B is a total computable function that has the property that each word w is in A if and only if f(w) is in B. If such a function f exists, one says that A is many-one reducible or m-reducible to B and writes

Subsets of natural numbers

Given two sets one says A is many-one reducible to B and writes if there exists a total computable function f with x\in A iff f(x)\in B. If the many-one reduction f is injective, one speaks of a one-one reduction and writes A \leq_1 B. If the one-one reduction f is surjective, one says A is recursively isomorphic to B and writes p.324

Many-one equivalence

If both and, one says A is many-one equivalent or m-equivalent to B and writes

Many-one completeness (m-completeness)

A set B is called many-one complete, or simply m-complete, iff B is recursively enumerable and every recursively enumerable set A is m-reducible to B.

Degrees

The relation \equiv_m indeed is an equivalence, its equivalence classes are called m-degrees and form a poset with the order induced by \leq_m. p.257 Some properties of the m-degrees, some of which differ from analogous properties of Turing degrees: 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. pp.574--575 Myhill's isomorphism theorem can be stated as follows: "For all sets A,B of natural numbers, ." As a corollary, \equiv and \equiv_1 have the same equivalence classes. p.325 The equivalences classes of \equiv_1 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 AC_0 or NC_0 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 A and B and an algorithm N that solves instances of B, we can use a many-one reduction from A to B to solve instances of A 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.

Many-one reductions extended

One may also ask about generalized cases of many-one reduction. One such example is e-reduction, where we consider f:A\to B that are recursively enumerable instead of restricting to recursive f. The resulting reducibility relation is denoted \leq_e, and its poset has been studied in a similar vein to that of the Turing degrees. For example, there is a jump set for e-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.

Properties

Karp reductions

A polynomial-time many-one reduction from a problem A to a problem B (both of which are usually required to be decision problems) is a polynomial-time algorithm for transforming inputs to problem A into inputs to problem B, such that the transformed problem has the same output as the original problem. 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. A reduction of this type is denoted by A \le_m^P B or A \le_p B.