Many-one reduction

In computability theory and computational complexity theory, a many-one reduction (also called mapping reduction^[1]) is a reduction that converts instances of one decision problem (whether an instance is in ${\displaystyle L_{1}}$) to another decision problem (whether an instance is in ${\displaystyle L_{2}}$) using a computable function. The reduced instance is in the language ${\displaystyle L_{2}}$ if and only if the initial instance is in its language ${\displaystyle L_{1}}$. Thus if we can decide whether ${\displaystyle L_{2}}$ instances are in the language ${\displaystyle L_{2}}$, we can decide whether ${\displaystyle L_{1}}$ instances are in its language by applying the reduction and solving for ${\displaystyle L_{2}}$. Thus, reductions can be used to measure the relative computational difficulty of two problems. It is said that ${\displaystyle L_{1}}$ reduces to ${\displaystyle L_{2}}$ if, in layman's terms ${\displaystyle L_{2}}$ is at least as hard to solve as ${\displaystyle L_{1}}$. This means that any algorithm that solves ${\displaystyle L_{2}}$ can also be used as part of a (otherwise relatively simple) program that solves ${\displaystyle L_{1}}$.

Many-one reductions are a special case and stronger form of Turing reductions.^[1] With many-one reductions, the oracle (that is, our solution for ${\displaystyle L_{2}}$) can be invoked only once at the end, and the answer cannot be modified. This means that if we want to show that problem ${\displaystyle L_{1}}$ can be reduced to problem ${\displaystyle L_{2}}$, we can use our solution for ${\displaystyle L_{2}}$ only once in our solution for ${\displaystyle L_{1}}$, unlike in Turing reductions, where we can use our solution for ${\displaystyle L_{2}}$ as many times as needed in order to solve the membership problem for the given instance of ${\displaystyle L_{1}}$.

Many-one reductions were first used by Emil Post in a paper published in 1944.^[2] Later Norman Shapiro used the same concept in 1956 under the name strong reducibility.^[3]