Many-one reduction

From Wikipedia, the free encyclopedia

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.

1 Definitions
2 Many-one reductions with resource limitations
3 Properties
4 References

[edit] Definitions

[edit] 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.$

[edit] 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.$

[edit] 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.$

[edit] 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.

[edit] 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$ .

[edit] 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

Retrieved from "http://en.wikipedia.org../../../m/a/n/Many-one_reduction.html"

Categories: Recursion theory | Computational complexity theory