Editing Many-one reduction

{{Short description|Type of Turing reduction}}
In [[computability theory]] and  [[computational complexity theory]], a '''many-one reduction''' (also called '''mapping reduction'''<ref name="Abrahamson2016">{{cite web|url=http://www.cs.ecu.edu/karl/6420/spr16/Notes/Reduction/mapping.html|title=Mapping reductions|work=CSCI 6420 – Computability and Complexity|date=Spring 2016|first=Karl R.|last=Abrahamson|publisher=East Carolina University|accessdate=2021-11-12}}</ref>) is a [[reduction (complexity)|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 reduction]]s.<ref name="Abrahamson2016"/> With many-one reductions, the oracle (that is, our solution for <math>L_2</math>) can be invoked only once at the end, and the answer cannot be modified. This means that if we want to show that problem <math>L_1</math> can be reduced to problem <math>L_2</math>, we can use our solution for <math>L_2</math> only once in our solution for <math>L_1</math>, unlike in Turing reductions, where we can use our solution for <math>L_2</math> as many times as needed in order to solve the membership problem for the given instance of <math>L_1</math>.

Many-one reductions were first used by [[Emil Post]] in a paper published in 1944.<ref>E. L. Post, "[https://web.archive.org/web/20180811064242/https://pdfs.semanticscholar.org/ed71/ebe0eee4f88f095247c8b62ba1d3b217a68d.pdf Recursively enumerable sets of positive integers and their decision problems]", [[Bulletin of the American Mathematical Society]] '''50''' (1944) 284–316</ref> Later [[Norman Shapiro]] used the same concept in 1956 under the name ''strong reducibility''.<ref>Norman Shapiro, "[https://web.archive.org/web/20180811065234/https://pdfs.semanticscholar.org/742b/cb582c02c9658888b8b4fb6191737a5c790c.pdf Degrees of Computability]", [[Transactions of the American Mathematical Society]] '''82''', (1956) 281–299</ref>

== Definitions ==

=== Formal languages ===

Suppose <math>A</math> and <math>B</math> are [[formal language]]s over the [[Alphabet (computer science)|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 function|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 function|surjective]], one says <math>A</math> is '''[[computable isomorphism|recursively isomorphic]]''' to <math>B</math> and writes<ref name="Odifreddi89">[[Piergiorgio Odifreddi|P. Odifreddi]], ''Classical Recursion Theory: The theory of functions and sets of natural numbers'' (p.320). Studies in Logic and the Foundations of Mathematics, vol. 125 (1989), Elsevier 0-444-87295-7.</ref><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 relation|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>.<ref name="Odifreddi89" /><sup>p.257</sup>

Some properties of the m-degrees, some of which differ from analogous properties of [[Turing degree|Turing degrees]]:<ref name="Odifreddi89" /><sup>pp.555--581</sup>
* There is a well-defined jump operator on the m-degrees.
* The only m-degree with jump '''0'''<sub>m</sub>&prime; is '''0'''<sub>m</sub>.
* There are m-degrees <math>\mathbf a>_m\boldsymbol 0_m'</math> where there does not exist <math>\mathbf b</math> where <math>\mathbf b'=\mathbf a</math>.
* Every countable linear order with a least element embeds into <math>\mathcal D_m</math>.
* The first order theory of <math>\mathcal D_m</math> is isomorphic to the theory of second-order arithmetic.

There is a characterization of <math>\mathcal D_m</math> as the unique poset satisfying several explicit properties of its [[Ideal_(set_theory)|ideals]], a similar characterization has eluded the Turing degrees.<ref name="Odifreddi89" /><sup>pp.574--575</sup>

[[Myhill isomorphism theorem|Myhill's isomorphism theorem]] can be stated as follows: "For all sets <math>A,B</math> of natural numbers, <math>A\equiv B\iff A\equiv_1 B</math>." As a corollary, <math>\equiv</math> and <math>\equiv_1</math> have the same equivalence classes.<ref name="Odifreddi89" /><sup>p.325</sup> The equivalences classes of <math>\equiv_1</math> are called the ''1-degrees''.

== 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, logarithmic space, by <math>AC_0</math> or <math>NC_0</math> circuits, or polylogarithmic projections where each subsequent reduction notion is weaker than the prior; see [[polynomial-time reduction]] and [[log-space reduction]] for details.

Given decision problems <math>A</math> and <math>B</math> and an [[algorithm]] ''N'' that solves instances of <math>B</math>, we can use a many-one reduction from <math>A</math> to <math>B</math> to solve instances of <math>A</math> 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 outside '''C''' to a language in '''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 it to a problem in '''C'''. Many-one reductions are valuable because most well-studied complexity classes are closed under some type of many-one reducibility, including [[P (complexity)|P]], [[NP (complexity)|NP]], [[L (complexity)|L]], [[NL (complexity)|NL]], [[co-NP]], [[PSPACE]], [[EXP]], and many others. It is known for example that the first four listed are closed up to the very weak reduction notion of polylogarithmic time projections.  These classes are not closed under arbitrary many-one reductions, however.

== Many-one reductions extended ==
One may also ask about generalized cases of many-one reduction. One such example is ''e-reduction'', where we consider <math>f:A\to B</math> that are recursively enumerable instead of restricting to recursive <math>f</math>. The resulting reducibility relation is denoted <math>\leq_e</math>, and its poset has been studied in a similar vein to that of the Turing degrees. For example, there is a jump set <math>\boldsymbol 0^'_e</math> for ''e''-degrees. The ''e''-degrees do admit some properties differing from those of the poset of Turing degrees, e.g. an embedding of the diamond graph into the degrees below <math>\boldsymbol'_e</math>.<ref>S. Ahmad, [https://www.jstor.org/stable/2274914 Embedding the Diamond in the <math>\Sigma_2</math> Enumeration Degrees] (1991). [[Journal of Symbolic Logic]], vol.56.</ref>

== Properties ==
* The [[relation (mathematics)|relation]]s of many-one reducibility and 1-reducibility are [[transitive relation|transitive]] and [[reflexive relation|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 [[Decidability (logic)|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 reduction|polynomial-time]] many-one reduction from a problem ''A'' to a problem ''B'' (both of which are usually required to be [[decision problem]]s) 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>.<ref name="goldreich">{{citation|title=Computational Complexity: A Conceptual Perspective|first=Oded|last=Goldreich|authorlink=Oded Goldreich|publisher=Cambridge University Press|year=2008|isbn=9781139472746|pages=59–60}}</ref><ref name = "kleinberg-tardos">{{cite book | last1=Kleinberg | first1=Jon|authorlink1= Jon Kleinberg| last2=Tardos | first2=Éva|authorlink2=Éva Tardos
|year=2006
|publisher=Pearson Education
|title=Algorithm Design
|isbn=978-0-321-37291-8
|pages=452–453
}}
</ref>

== References ==
{{reflist}}

[[Category:Reduction (complexity)]]