Many-one reduction
Type of Turing reduction / From Wikipedia, the free encyclopedia
Dear Wikiwand AI, let's keep it short by simply answering these key questions:
Can you list the top facts and stats about Many-one reduction?
Summarize this article for a 10 year old
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 ) to another decision problem (whether an instance is in ) using a computable function. The reduced instance is in the language if and only if the initial instance is in its language . Thus if we can decide whether instances are in the language , we can decide whether instances are in its language by applying the reduction and solving for . Thus, reductions can be used to measure the relative computational difficulty of two problems. It is said that reduces to if, in layman's terms is at least as hard to solve as . This means that any algorithm that solves can also be used as part of a (otherwise relatively simple) program that solves .
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 ) can be invoked only once at the end, and the answer cannot be modified. This means that if we want to show that problem can be reduced to problem , we can use our solution for only once in our solution for , unlike in Turing reductions, where we can use our solution for as many times as needed in order to solve the membership problem for the given instance of .
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]