|
In computational complexity theory, a Turing reduction from a problem A to a problem B is, intuitively, a reduction which easily solves B, assuming A is easy to solve. More formally, a Turing reduction is a function computable by an oracle 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 problems and function problems.
If CC = 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 ∈ C. Many important complexity classes such as 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, such as L, NL, SL, and P itself, are closed under Turing reductions.
Where Turing reductions are too powerful, a special case called many-one reductions 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
|
