Many-one reduction
In computability theory and computational complexity theory, a many-one reduction is a reduction which converts instances of one decision problem into instances of a second decision problem. Reductions are thus used to measure the relative computational difficulty of two problems. It is said that A reduces to B if, in layman's terms, B is harder to solve than A. That is to say, any algorithm that solves B can also be used as part of a (otherwise relatively simple) program that solves A.
Many-one reductions are a special case and stronger form of Turing reductions. With many-one reductions the oracle (That is, our solution for B) can be invoked only once at the end and the answer cannot be modified. This means that if we want to show that problem A can be reduced to problem B, we can use our solution for A only once in our solution for B, unlike in Turing reduction, where we can use our solution for A as many times as needed while solving B.
Practically, this means that Many-one reductions map instances of one problem to instances of another, while Turing reductions compute the solution to one problem, assuming the other problem is easy to solve. The many-one reduction is more effective at separating problems into distinct complexity classes. However, the increased restrictions on many-one reductions make them more difficult to find.
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.
Suppose A and B are formal languages over the alphabets Σ and Γ, respectively. A many-one reduction from A to B is a total computable function f : Σ* → Γ* that has the property that each word w is in A if and only if f(w) is in B (that is, ).
...
Wikipedia