Many-one reduction

Summary

A many-one reduction from a set $A$ to a set $B$ of natural numbers is a total computable function $f$ with $x \in A$ exactly when $f(x) \in B$. It turns every question about membership in $A$ into one question about membership in $B$. Many-one reductions compare how hard decision problems are, and they are the standard tool for proving that a problem is undecidable.