Many-one reducibility

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.

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$.

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