Many-one reduction

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

Many-one reductions are a special case and a 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 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 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 function 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 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 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 \leq_m B if and only if \mathbb{N} \setminus A \leq_m \mathbb{N} \setminus 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 many-one 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.

References


Wikimedia Foundation. 2010.

Игры ⚽ Нужен реферат?

Look at other dictionaries:

  • Reduction (complexity) — Example of a reduction from a boolean satisfiability problem to a vertex cover problem. Blue vertices form a vertex cover which corresponds to truth values. In computability theory and computational complexity theory, a reduction is a… …   Wikipedia

  • Reduction (recursion theory) — In computability theory, many reducibility relations (also called reductions, reducibilities, and notions of reducibility) are studied. They are motivated by the question: given sets A and B of natural numbers, is it possible to effectively… …   Wikipedia

  • Turing reduction — In computability theory, a Turing reduction from a problem A to a problem B, named after Alan Turing, is a reduction which solves A, assuming B is already known (Rogers 1967, Soare 1987). It can be understood as an algorithm that could be used to …   Wikipedia

  • Reduction potential — (also known as redox potential, oxidation / reduction potential, ORP or Eh) is a measure of the tendency of a chemical species to acquire electrons and thereby be reduced. Reduction potential is measured in volts (V), or millivolts (mV). Each… …   Wikipedia

  • Polynomial-time reduction — In computational complexity theory a polynomial time reduction is a reduction which is computable by a deterministic Turing machine in polynomial time. If it is a many one reduction, it is called a polynomial time many one reduction, polynomial… …   Wikipedia

  • Log-space reduction — In computational complexity theory, a log space reduction is a reduction computable by a deterministic Turing machine using logarithmic space. Conceptually, this means it can keep a constant number of pointers into the input, along with a… …   Wikipedia

  • One-Two-GO Airlines Flight 269 — Crash scene Accident summary Date September 16 2007 …   Wikipedia

  • One Hundred Years of Solitude —   …   Wikipedia

  • PTAS reduction — In computational complexity theory, a PTAS reduction is a reduction that is often used to perform reductions between solutions to optimization problems. It preserves the property that a problem has a polynomial time approximation scheme (PTAS)… …   Wikipedia

  • One Atlantic Center — One and Two Atlantic Center Alternative names IBM Tower General information Type C …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”