 Manyone reduction

In computability theory and computational complexity theory, a manyone reduction is a reduction which converts instances of one decision problem into instances of a second decision problem. Reductions are thus used to measure the relative computational difficulty of two problems.
Manyone reductions are a special case and a stronger form of Turing reductions. With manyone reductions the oracle can be invoked only once at the end and the answer cannot be modified.
Manyone reductions were first used by Emil Post in 1944. Later Norman Shapiro used the same concept in 1956 under the name strong reducibility.
Contents
Definitions
Formal languages
Suppose A and B are formal languages over the alphabets Σ and Γ, respectively. A manyone reduction from A to B is a total computable function f : Σ^{*} → Γ^{*} that has the property that each word w is in A if and only if f(w) is in B (that is, A = f ^{− 1}(B)).
If such a function f exists, we say that A is manyone reducible or mreducible to B and write
If there is an injective manyone reduction function then we say A is 1 reducible or oneone reducible to B and write
Subsets of natural numbers
Given two sets we say A is manyone reducible to B and write
if there exists a total computable function f with A = f ^{− 1}(B). If additionally f is injective we say A is 1reducible to B and write
Manyone equivalence and 1 equivalence
If we say A is manyone equivalent or mequivalent to B and write
If we say A is 1equivalent to B and write
Manyone completeness (mcompleteness)
A set B is called manyone complete, or simply mcomplete, iff B is recursively enumerable and every recursively enumerable set A is mreducible to B.
Manyone reductions with resource limitations
Manyone reductions are often subjected to resource restrictions, for example that the reduction function is computable in polynomial time or logarithmic space; see polynomialtime reduction and logspace reduction for details.
Given decision problems A and B and an algorithm N which solves instances of B, we can use a manyone reduction from A to B to solve instances of A 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 manyone reducibility if there exists no reduction from a language in C to a language outside C. If a class is closed under manyone reducibility, then manyone reduction can be used to show that a problem is in C by reducing a problem in C to it. Manyone reductions are valuable because most wellstudied complexity classes are closed under some type of manyone reducibility, including P, NP, L, NL, coNP, PSPACE, EXP, and many others. These classes are not closed under arbitrary manyone reductions, however.
Properties
 The relations of manyone reducibility and 1 reducibility are transitive and reflexive and thus induce a preorder on the powerset of the natural numbers.
 if and only if
 A set is manyone reducible to the halting problem if and only if it is recursively enumerable. This says that with regards to manyone reducibility, the halting problem is the most complicated of all computer programs. Thus the halting problem is manyone complete.
 The specialized halting problem for an individual Turing machine T (i.e., the set of inputs for which T eventually halts) is manyone complete iff T is a universal Turing machine. Emil Post showed that there exist recursively enumerable sets that are neither decidable nor mcomplete, and hence that there exist nonuniversal Turing machines whose individual halting problems are nevertheless undecidable.
References
 E. L. Post, "Recursively enumerable sets of positive integers and their decision problems", Bulletin of the American Mathematical Society 50 (1944) 284316
 Norman Shapiro, "Degrees of Computability", Transactions of the American Mathematical Society 82, (1956) 281299
Wikimedia Foundation. 2010.