In computability theory and computational complexity theory, a many-one reduction (also called mapping reduction) is a reduction that converts instances of one decision problem (whether an instance is in <math>L_1</math>) to another decision problem (whether an instance is in <math>L_2</math>) using a computable function. The reduced instance is in the language <math>L_2</math> if and only if the initial instance is in its language <math>L_1</math>. Thus if we can decide whether <math>L_2</math> instances are in the language <math>L_2</math>, we can decide whether <math>L_1</math> instances are in the language <math>L_1</math> by applying the reduction and solving for <math>L_2</math>. Thus, reductions can be used to measure the relative computational difficulty of two problems. It is said that <math>L_1</math> reduces to <math>L_2</math> if, in layman's terms <math>L_2</math> is at least as hard to solve as <math>L_1</math>. This means that any algorithm that solves <math>L_2</math> can also be used as part of a (otherwise relatively simple) program that solves <math>L_1</math>.
Many-one reductions are a special case and stronger form of Turing reductions. Later Norman Shapiro used the same concept in 1956 under the name strong reducibility.
Definitions
Formal languages
Suppose <math>A</math> and <math>B</math> are formal languages over the alphabets <math>\Sigma</math> and <math>\Gamma</math>, respectively. A many-one reduction from <math>A</math> to <math>B</math> is a total computable function <math>f: \Sigma^{*}\rightarrow\Gamma^{*}</math> that has the property that each word <math>w</math> is in <math>A</math> if and only if <math>f(w)</math> is in <math>B</math>.
If such a function <math>f</math> exists, one says that <math>A</math> is many-one reducible or m-reducible to <math>B</math> and writes
:<math>A \leq_{\mathrm{m B.</math>
Subsets of natural numbers
Given two sets <math>A,B \subseteq \mathbb{N}</math> one says <math>A</math> is many-one reducible to <math>B</math> and writes
:<math>A \leq_{\mathrm{m B</math>
if there exists a total computable function <math>f</math> with <math>x\in A</math> iff <math>f(x)\in B</math>.
If the many-one reduction <math>f</math> is injective, one speaks of a one-one reduction and writes <math>A \leq_1 B</math>.
If the one-one reduction <math>f</math> is surjective, one says <math>A</math> is recursively isomorphic to <math>B</math> and writes<sup>p.324</sup>
:<math>A\equiv B</math>
Many-one equivalence
If both <math>A \leq_{\mathrm{m B</math> and <math>B \leq_{\mathrm{m A</math>, one says <math>A</math> is many-one equivalent or m-equivalent to <math>B</math> and writes
:<math>A \equiv_{\mathrm{m B.</math>
Many-one completeness (m-completeness)
A set <math>B</math> is called many-one complete, or simply m-complete, iff <math>B</math> is recursively enumerable and every recursively enumerable set <math>A</math> is m-reducible to <math>B</math>.
Degrees
The relation <math>\equiv_m</math> indeed is an equivalence, its equivalence classes are called m-degrees and form a poset <math>\mathcal D_m</math> with the order induced by <math>\leq_m</math>.
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.
- <math>A \leq_{\mathrm{m B</math> if and only if <math>\mathbb{N} \setminus A \leq_{\mathrm{m \mathbb{N} \setminus B.</math>
- 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 recursively enumerable problems. Thus the halting problem is r.e. complete. Note that it is not the only r.e. complete problem.
- 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 <u>non</u>universal Turing machines whose individual halting problems are nevertheless undecidable.
Karp reductions
A polynomial-time many-one reduction from a problem A to a problem B (both of which are usually required to be decision problems) is a polynomial-time algorithm for transforming inputs to problem A into inputs to problem B, such that the transformed problem has the same output as the original problem. An instance x of problem A can be solved by applying this transformation to produce an instance y of problem B, giving y as the input to an algorithm for problem B, and returning its output. Polynomial-time many-one reductions may also be known as polynomial transformations or Karp reductions, named after Richard Karp. A reduction of this type is denoted by <math>A \le_m^P B</math> or <math>A \le_p B</math>.