Many-one reduction
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 formula_1 into instances of a second decision problem formula_2 where the instance reduced to is in the language formula_2 if the initial instance was in its language formula_1 and is not in the language formula_2 if the initial instance was not in its language formula_1. Thus if we can decide whether formula_2 instances are in the language formula_2, we can decide whether formula_1 instances are in its language by applying the reduction  and solving formula_2. Thus, reductions can be used to measure the relative computational difficulty of two problems. It is said that formula_1 reduces to formula_2 if, in layman's terms formula_2 is harder to solve than formula_1. That is to say, any algorithm that solves formula_2 can also be used as part of a (otherwise relatively simple) program that solves formula_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 B) can be invoked only once at the end, and the answer cannot be  modified. This means that if we want to show that problem A can be reduced to problem B, we can use our solution for B only once in our solution for A, unlike in Turing reduction, where we can use our solution for B as many times as needed while solving A. This means that many-one reductions map instances of one problem to instances of another, while Turing reductions compute the solution to one problem, assuming the other problem is easy to solve. The many-one reduction is more effective at separating problems into distinct complexity classes. However, the  increased restrictions on many-one reductions make them more difficult to find. 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 formula_17 and formula_18 are formal languages over the alphabets formula_19 and formula_20, respectively. A many-one reduction from formula_17 to formula_18 is a total computable function formula_23 that has the property that each word formula_24 is in formula_17 if and only if formula_26 is in formula_18. If such a function formula_28 exists, we say that  formula_17 is many-one reducible or m-reducible to formula_18 and write If there is an injective many-one reduction function then we say "A" is 1-reducible or one-one reducible to formula_18 and write Subsets of natural numbers. Given two sets formula_34 we say formula_17 is many-one reducible to formula_18 and write if there exists a total computable function formula_28 with formula_39 If additionally formula_28 is injective we say formula_17 is 1-reducible to formula_18 and write Many-one equivalence and 1-equivalence. If formula_44 we say formula_17 is many-one equivalent or m-equivalent to formula_18  and write If formula_48 we say formula_17 is 1-equivalent to formula_18 and write Many-one completeness (m-completeness). A set formula_18 is called "many-one complete", or simply m-complete, iff formula_18 is recursively enumerable and every recursively enumerable set formula_17 is m-reducible to formula_18. 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 formula_56 or formula_57 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 formula_17 and formula_18 and an algorithm "N" which solves instances of formula_18, we can use a many-one reduction from formula_17 to formula_18 to solve instances of formula_17 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 in C to a language outside 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 a problem in C to it. 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. 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 formula_66 or formula_67.