Editing Many-one reduction (section)

{{Short description|Type of Turing reduction}}
In [[computability theory]] and  [[computational complexity theory]], a '''many-one reduction''' (also called '''mapping reduction'''<ref name="Abrahamson2016">{{cite web|url=http://www.cs.ecu.edu/karl/6420/spr16/Notes/Reduction/mapping.html|title=Mapping reductions|work=CSCI 6420 – Computability and Complexity|date=Spring 2016|first=Karl R.|last=Abrahamson|publisher=East Carolina University|accessdate=2021-11-12}}</ref>) is a [[reduction (complexity)|reduction]] that converts instances of one [[decision problem]] (whether an instance is in <math>L_1</math>) to another decision problem (whether an instance is in <math>L_2</math>) using a [[computable function]]. The reduced instance is in the language <math>L_2</math> if and only if the initial instance is in its language <math>L_1</math>. Thus if we can decide whether <math>L_2</math> instances are in the language <math>L_2</math>, we can decide whether <math>L_1</math> instances are in the language <math>L_1</math> by applying the reduction and solving for <math>L_2</math>. Thus, reductions can be used to measure the relative computational difficulty of two problems. It is said that <math>L_1</math> reduces to <math>L_2</math> if, in layman's terms <math>L_2</math> is at least as hard to solve as <math>L_1</math>. This means that any algorithm that solves <math>L_2</math> can also be used as part of a (otherwise relatively simple) program that solves <math>L_1</math>.

Many-one reductions are a special case and stronger form of [[Turing reduction]]s.<ref name="Abrahamson2016"/> With many-one reductions, the oracle (that is, our solution for <math>L_2</math>) can be invoked only once at the end, and the answer cannot be modified. This means that if we want to show that problem <math>L_1</math> can be reduced to problem <math>L_2</math>, we can use our solution for <math>L_2</math> only once in our solution for <math>L_1</math>, unlike in Turing reductions, where we can use our solution for <math>L_2</math> as many times as needed in order to solve the membership problem for the given instance of <math>L_1</math>.

Many-one reductions were first used by [[Emil Post]] in a paper published in 1944.<ref>E. L. Post, "[https://web.archive.org/web/20180811064242/https://pdfs.semanticscholar.org/ed71/ebe0eee4f88f095247c8b62ba1d3b217a68d.pdf Recursively enumerable sets of positive integers and their decision problems]", [[Bulletin of the American Mathematical Society]] '''50''' (1944) 284–316</ref> Later [[Norman Shapiro]] used the same concept in 1956 under the name ''strong reducibility''.<ref>Norman Shapiro, "[https://web.archive.org/web/20180811065234/https://pdfs.semanticscholar.org/742b/cb582c02c9658888b8b4fb6191737a5c790c.pdf Degrees of Computability]", [[Transactions of the American Mathematical Society]] '''82''', (1956) 281–299</ref>