Difference between revisions 1188375 and 1188424 on enwiki

In [[computational complexity theory]], a '''Turing reduction''' from a problem A to a problem B is, intuitively, a [[reduction (complexity)|reduction]] which easily solves B, assuming A is easy to solve. More formally, a Turing reduction is a function computable by aThe following Wikipedians live in [[Noracle machine]] with an oracle for A.

If such a reduction exists, then every [[algorithm]] for ''M'' immediately yields an algorithm for ''L'', formed by inserting a "call" to that algorithm at each place where the oracle machine uses it. However, because the oracle machine may invoke the algorithm a large number of times, the resulting algorithm may require more time asymptotically than either ''M'' or the oracle machine, and require as much space as both together. Turing reductions can be applied to both [[decision problem]]s and [[function problem]]s. 

If C<sup>C</sup> = C for some class of problems C, we say that C is ''closed under Turing reductions''. Demonstrating a Turing reduction from a problem A to a problem in such a class C shows that A &isin; C. Many important [[complexity class]]es such as [[NP (complexity)|NP]] are not closed under Turing reductions. In particular, any decision problem can be Turing-reduced to its complement, by simply solving the original problem and inverting the answer, showing that any class not closed under complement is also not closed under Turing reductions. However, a number of classes within [[P (complexity)|P]], such as [[L (complexity)|L]], [[NL (complexity)|NL]], [[SL (complexity)|SL]], and [[P (complexity)|P]] itself, are closed under Turing reductions.

Where Turing reductions are too powerful, a special case called [[many-one reduction]]s are usually used instead; most natural complexity classes are closed under these. These can be seen as Turing reductions where the oracle can only be invoked one time at the end of the oracle machine's processing.

Turing reductions are often subjected to additional resource restrictions, for example that the oracle machine runs in polynomial time or logarithmic space; see [[polynomial-time reduction]] and [[log-space reduction]] for details.

== References ==
* [http://www.nist.gov/dads/HTML/turingredctn.html NIST Dictionary of Algorithms and Data Structures: Turing reduction]

[[Category:Computational complexity theoryway]]:

* [[User:Eirik|Eirik Birkeland]]
* [[User:Espen|Espen Andersen]]
* [[User:gisle|Gisle Hannemyr]]
* [[Joakim Ziegler]]
* [[User:Ole_Aamot|Ole Aamot]]
* [[User:Lazyr|Lauritz Thaulow]]
:''See also :'' [[Wikipedians]]