Many-one reduction

From Free net encyclopedia

In computational complexity theory, a many-one reduction is a reduction which converts instances of a decision problem problem A into instances of a decision problem B. If we have an algorithm N which solves instances of B, we can use it 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.

Many-one reductions are a special case and a weaker form of Turing reductions where only one invocation of the oracle is allowed, and only at the end. Turing reductions are sometimes more convenient for designing reduction algorithms, but their power also causes several important classes such as NP to not be closed under Turing reductions.

Many-one reductions are often subjected to additional resource restrictions, for example that the function is computable in polynomial time or logarithmic space; see polynomial-time reduction and log-space reduction for details.

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

[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

<math> 
 w\in A \Leftrightarrow f(w)\in B\qquad\forall w\in\Sigma^*.

</math> If such a function f exists, we say that "A is many-one reducible to B".

[edit]

Subsets of natural numbers

Given two sets <math>A,B \subseteq \mathbb{N}</math> we say <math>A</math> is many-one reducible or m-reducible to <math>B</math> and write

<math>A \leq_m B</math>

if there exists a total computable function <math>f</math> with

<math>A = f^{-1}[B].</math>

If additionally <math>f</math> is injective we say <math>A</math> is 1-reducible to <math>B</math> and write

<math>A \leq_1 B.</math>

If

<math>A \leq_m B \, \mathrm{and} \, B \leq_m A</math>

we say <math>A</math> is many-one equivalent or m-equivalent to <math>B</math> and write

<math>A \equiv_m B.</math>

If

<math>A \leq_1 B \, \mathrm{and} \, B \leq_1 A</math>

we say <math>A</math> is 1-equivalent to <math>B</math> and write

<math>A \equiv_1 B.</math>
[edit]

Remarks

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.

[edit]

Properties

  • the relation many-one reducibility and 1 reducibility are transitive and reflexive and thus induce a partial order on the powerset of the natural numbers.
  • if <math>A \le B</math> then <math>\mathbb{N} \setminus A \le \mathbb{N} \setminus B</math>
[edit]

References

Retrieved from "http://www.netipedia.com/index.php/Many-one_reduction"