# Many-one reducibility

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
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.