In computability theory and computational complexity theory, a many-one reduction (also called mapping reduction) is a reduction that converts instances of one decision problem (whether an instance is in L 1 {\displaystyle L_{1}} ) to another decision problem (whether an instance is in L 2 {\displaystyle L_{2}} ) using a computable function. The reduced instance is in the language L 2 {\displaystyle L_{2}} if and only if the initial instance is in its language L 1 {\displaystyle L_{1}} . Thus if we can decide whether L 2 {\displaystyle L_{2}} instances are in the language L 2 {\displaystyle L_{2}} , we can decide whether L 1 {\displaystyle L_{1}} instances are in the language L 1 {\displaystyle L_{1}} by applying the reduction and solving for L 2 {\displaystyle L_{2}} . Thus, reductions can be used to measure the relative computational difficulty of two problems. It is said that L 1 {\displaystyle L_{1}} reduces to L 2 {\displaystyle L_{2}} if, in layman's terms L 2 {\displaystyle L_{2}} is at least as hard to solve as L 1 {\displaystyle L_{1}} . This means that any algorithm that solves L 2 {\displaystyle L_{2}} can also be used as part of a (otherwise relatively simple) program that solves L 1 {\displaystyle L_{1}} . Many-one reductions are a special case and stronger form of Turing reductions. With many-one reductions, the oracle (that is, our solution for L 2 {\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 L 1 {\displaystyle L_{1}} can be reduced to problem L 2 {\displaystyle L_{2}} , we can use our solution for L 2 {\displaystyle L_{2}} only once in our solution for L 1 {\displaystyle L_{1}} , unlike in Turing reductions, where we can use our solution for L 2 {\displaystyle L_{2}} as many times as needed in order to solve the membership problem for the given instance of L 1 {\displaystyle L_{1}} . Many-one reductions were first used by Emil Post in a paper published in 1944. Later Norman Shapiro used the same concept in 1956 under the name strong reducibility.
Definitions
Formal languages Suppose A {\displaystyle A} and B {\displaystyle B} are formal languages over the alphabets Σ {\displaystyle \Sigma } and Γ {\displaystyle \Gamma } , respectively. A many-one reduction from A {\displaystyle A} to B {\displaystyle B} is a total computable function f : Σ ∗ → Γ ∗ {\displaystyle f:\Sigma ^{*}\rightarrow \Gamma ^{*}} that has the property that each word w {\displaystyle w} is in A {\displaystyle A} if and only if f ( w ) {\displaystyle f(w)} is in B {\displaystyle B} . If such a function f {\displaystyle f} exists, one says that A {\displaystyle A} is many-one reducible or m-reducible to B {\displaystyle B} and writes
A ≤ m B . {\displaystyle A\leq _{\mathrm {m} }B.}
Subsets of natural numbers Given two sets A , B ⊆ N {\displaystyle A,B\subseteq \mathbb {N} } one says A {\displaystyle A} is many-one reducible to B {\displaystyle B} and writes
A ≤ m B {\displaystyle A\leq _{\mathrm {m} }B}
… excerpt ends here. Continue reading the full article.
