# Many-one reducibility

From Encyclopedia of Mathematics

Revision as of 22:08, 16 January 2016 by Richard Pinch (talk | contribs) (Start article: 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.

#### References

- Nicholas Pippenger
*Theories of Computability*Cambridge University Press (1997) ISBN 0-521-55380-6

**How to Cite This Entry:**

Many-one reducibility.

*Encyclopedia of Mathematics.*URL: http://encyclopediaofmath.org/index.php?title=Many-one_reducibility&oldid=37575