Puneet Varma (Editor)

Many one reduction

Updated on
Edit
Like
Comment
Share on FacebookTweet on TwitterShare on LinkedInShare on Reddit

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. Reductions are thus used to measure the relative computational difficulty of two problems.

Contents

Many-one reductions are a special case and stronger form of Turing reductions. With many-one reductions the oracle can be invoked only once at the end and the answer cannot be modified.

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.

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 ≤ m B .

If there is an injective many-one reduction function then we say A is 1-reducible or one-one reducible to B and write

A ≤ 1 B .

Subsets of natural numbers

Given two sets A , B ⊆ N we say A is many-one reducible to B and write

A ≤ 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 ≤ 1 B .

Many-one equivalence and 1-equivalence

If A ≤ m B a n d B ≤ m A we say A is many-one equivalent or m-equivalent to B and write

A ≡ m B .

If A ≤ 1 B a n d B ≤ 1 A we say A is 1-equivalent to B and write

A ≡ 1 B .

Many-one completeness (m-completeness)

A set B is called many-one complete, or simply m-complete, iff B is recursively enumerable and every recursively enumerable set A is m-reducible to 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 preorder on the powerset of the natural numbers.
  • A ≤ m B if and only if N ∖ A ≤ m N ∖ B .
  • A set is many-one reducible to the halting problem if and only if it is recursively enumerable. This says that with regards to many-one reducibility, the halting problem is the most complicated of all computer programs. Thus the halting problem is r.e. complete.
  • The specialized halting problem for an individual Turing machine T (i.e., the set of inputs for which T eventually halts) is many-one complete iff T is a universal Turing machine. Emil Post showed that there exist recursively enumerable sets that are neither decidable nor m-complete, and hence that there exist nonuniversal Turing machines whose individual halting problems are nevertheless undecidable.

    • Reading

  • 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

    • References

    Many-one reduction Wikipedia
    (Text) CC BY-SA