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.
Many-one reductions are a special case and stronger form of Turing reductions. With many-one reductions the oracle can be invoked only once at the end and the answer cannot be modified.
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.
Read more about Many-one Reduction: Many-one Reductions With Resource Limitations, Properties
Famous quotes containing the word reduction:
“The reduction of nuclear arsenals and the removal of the threat of worldwide nuclear destruction is a measure, in my judgment, of the power and strength of a great nation.”
—Jimmy Carter (James Earl Carter, Jr.)