Namespaces
Variants
Actions

Difference between revisions of "Many-one reducibility"

From Encyclopedia of Mathematics
Jump to: navigation, search
(more, cite Nies (2009))
(define one-one reducibility)
Line 1: Line 1:
A relation between sets of natural numbers.  We say that $A$ is many-one reducible to $B$, $A \le_{\mathrm{m}} B$, if there is a general [[recursive function]] $\phi$ such that $x \in A$ if and only if $\phi(x) \in B$.  This defines a [[pre-order]] on sets of natural numbers, and the equivalence classes are $\mathrm{m}$-degrees; they refine the Turing degrees.
+
A relation between sets of natural numbers, expressing the notion of relative difficulty of computation.  We say that $A$ is ''many-one reducible'' ($\mathrm{m}$-reducible) to $B$, $A \le_{\mathrm{m}} B$, if there is a general [[recursive function]] $\phi$ such that $x \in A$ if and only if $\phi(x) \in B$.  This defines a [[pre-order]] on sets of natural numbers, and the equivalence classes are $\mathrm{m}$-degrees; they refine the Turing degrees.
  
 
Many-one reducibility is an instance of a [[truth-table reducibility]]: it implies [[Turing reducibility]], but not conversely.
 
Many-one reducibility is an instance of a [[truth-table reducibility]]: it implies [[Turing reducibility]], but not conversely.
  
 
Many-one reduction may also be regarded as a relation between functions on natural numbers: in this case, the [[characteristic function]]s of sets of natural numbers, with the pre-order $f  \le_{\mathrm{m}} g$ if there is a recursive $\phi$ such that $f(x) = g(\phi(x))$ for all $x$.
 
Many-one reduction may also be regarded as a relation between functions on natural numbers: in this case, the [[characteristic function]]s of sets of natural numbers, with the pre-order $f  \le_{\mathrm{m}} g$ if there is a recursive $\phi$ such that $f(x) = g(\phi(x))$ for all $x$.
 +
 +
We obtain the relation of ''$1$-reducibility'' (one-one reducibility) $A \le_{1} B$ if we restrict $\phi$ in this definition to being an [[injection]].  This is a strictly weaker notion.  Sets $A$,$B$ are $1$-equivalent if and only if there is a computable permutation $\pi$ of $\mathbf{N}$ that maps $A$ onto $B$.  The classes of $1$-complete, $\mathrm{m}$-complete and [[creative set]]s coincide.
  
 
====References====
 
====References====
 
* Nies, André ''Computability and randomness'' Oxford Logic Guides '''51''' Oxford University Press (2009)  ISBN 0-19-923076-1 {{ZBL|1169.03034}}
 
* Nies, André ''Computability and randomness'' Oxford Logic Guides '''51''' Oxford University Press (2009)  ISBN 0-19-923076-1 {{ZBL|1169.03034}}
 
* Pippenger, Nicholas  ''Theories of Computability'' Cambridge University Press (1997) ISBN 0-521-55380-6 {{ZBL|1200.03025}}
 
* Pippenger, Nicholas  ''Theories of Computability'' Cambridge University Press (1997) ISBN 0-521-55380-6 {{ZBL|1200.03025}}

Revision as of 19:21, 17 January 2016

A relation between sets of natural numbers, expressing the notion of relative difficulty of computation. We say that $A$ is many-one reducible ($\mathrm{m}$-reducible) to $B$, $A \le_{\mathrm{m}} B$, if there is a general recursive function $\phi$ such that $x \in A$ if and only if $\phi(x) \in B$. This defines a pre-order on sets of natural numbers, and the equivalence classes are $\mathrm{m}$-degrees; they refine the Turing degrees.

Many-one reducibility is an instance of a truth-table reducibility: it implies Turing reducibility, but not conversely.

Many-one reduction may also be regarded as a relation between functions on natural numbers: in this case, the characteristic functions of sets of natural numbers, with the pre-order $f \le_{\mathrm{m}} g$ if there is a recursive $\phi$ such that $f(x) = g(\phi(x))$ for all $x$.

We obtain the relation of $1$-reducibility (one-one reducibility) $A \le_{1} B$ if we restrict $\phi$ in this definition to being an injection. This is a strictly weaker notion. Sets $A$,$B$ are $1$-equivalent if and only if there is a computable permutation $\pi$ of $\mathbf{N}$ that maps $A$ onto $B$. The classes of $1$-complete, $\mathrm{m}$-complete and creative sets coincide.

References

  • Nies, André Computability and randomness Oxford Logic Guides 51 Oxford University Press (2009) ISBN 0-19-923076-1 Zbl 1169.03034
  • Pippenger, Nicholas Theories of Computability Cambridge University Press (1997) ISBN 0-521-55380-6 Zbl 1200.03025
How to Cite This Entry:
Many-one reducibility. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Many-one_reducibility&oldid=37584