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

  • 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

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

  • One Hundred Years of Solitude —   …   Wikipedia

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

  • One-child policy — Government sign in Tang Shan: For a prosperous, powerful nation and a happy family, please practice family planning. The one child policy (simplified Chinese: 计划生育政策; traditional Chinese: 計劃生育政策; pinyin: jìhuà shēngyù zhèngcè; literally policy of …   Wikipedia

  • Reduction of nitro compounds — The chemical reactions described as reduction of nitro compounds can be facilitated by many different reagents and reaction conditions. Historically, the nitro group was one of the first functional groups to be reduced, due to the ease of nitro… …   Wikipedia

  • Reduction of the structure group — In mathematics, in particular the theory of principal bundles, one can ask if a G bundle comes from a subgroup H < G. This is called reduction of the structure group (to H), and makes sense for any map H o G, which need not be an inclusion… …   Wikipedia

  • One-platoon system — The one platoon system, also known as iron man football, was a system in American football where players played on both offense and defense. It was the result of rules that limited player substitutions. The alternative system is known as the two… …   Wikipedia

Share the article and excerpts

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