MANY-ONE REDUCTION

In computability theory and computational complexity theory, a 'many-one reduction' is a reduction which converts instances of one decision problem into instances of a second decision problem.
Many-one reductions are a special case and a weaker form of Turing reductions. With many-one reductions only one invocation of the oracle is allowed, and only at the end.
Many-one 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

Subsets of natural numbers

Many-one equivalence and 1 equivalence

Many-one reductions with resource limitations

Properties

References

Definitions

Formal languages

Suppose ''A'' and ''B'' are formal languages over the alphabets Σ and Γ, respectively. A 'many-one 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 'many-one reducible' or 'm-reducible' to ''B'' and write
:$A\; leq\_m\; B.$
If there is an injective many-one reduction then we say ''A'' is '1 reducible' or 'one-one reducible' to ''B'' and write
:$A\; leq\_1\; B.$

Subsets of natural numbers

Given two sets $A,B\; subseteq\; mathbb\{N\}$ we say $A$ is 'many-one reducible' or to $B$ and write
:$A\; leq\_m\; B$
if there exists a total computable function $f$ with $A\; =\; f^\{-1\}[B].$
If additionally $f$ is injective we say $A$ is '1-reducible' to $B$ and write
:$A\; leq\_1\; B.$

Many-one equivalence and 1 equivalence

If $A\; leq\_m\; B\; ,\; mathrm\{and\}\; ,\; B\; leq\_m\; A$
we say $A$ is 'many-one equivalent' or 'm-equivalent' to $B$ and write
:$A\; equiv\_m\; B.$
If $A\; leq\_1\; B\; ,\; mathrm\{and\}\; ,\; B\; leq\_1\; A$
we say $A$ is '1-equivalent' to $B$ and write
:$A\; equiv\_1\; B.$

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 or logarithmic space; see polynomial-time reduction and log-space reduction for details.
Given decision problems ''A'' and ''B'' and an algorithm ''N'' which solves instances of B, we can use a many-one 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 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. These classes are not closed under arbitrary many-one reductions, however.

Properties

★ The relations of many-one reducibility and 1 reducibility are transitive and reflexive and thus induce a partial order on the powerset of the natural numbers.

★ If $A\; leq\_m\; B$ then $mathbb\{N\}\; setminus\; A\; leq\_m\; mathbb\{N\}\; setminus\; B$.

References

★ E. L. Post, "Recursively enumerable sets of positive integers and their decision problems", Bulletin of the American Mathematical Society '50' (1944) 284-316

★ Norman Shapiro, "Degrees of Computability", Transactions of the American Mathematical Society '82', (1956) 281-299