Turing Reduction - Stronger Reductions

Stronger Reductions

There are two common ways of producing reductions stronger than Turing reducibility. The first way is to limit the number and manner of oracle queries.

• A set A is many-one reducible to B if there is a total computable function f such that an element n is in A if and only if f(n) is in B. Such a function can be used to generate a Turing reduction (by computing f(n), querying the oracle, and then interpreting the result).
• A truth table reduction or a weak truth table reduction must present all of its oracle queries at the same time. In a truth table reduction, the reduction also gives a boolean function (a truth table) which, when given the answers to the queries, will produce the final answer of the reduction. In a weak truth table reduction, the reduction uses the oracle answers as a basis for further computation depending on the given answers (but not using the oracle). Equivalently, a weak truth table reduction is one for which the use of the reduction is bounded by a computable function. For this reason, weak truth table reductions are sometimes called "bounded Turing" reductions.

The second way to produce a stronger reducibility notion is to limit the computational resources that the program implementing the Turing reduction may use. These limits on the computational complexity of the reduction are important when studying subrecursive classes such as P. A set A is polynomial-time reducible to a set B if there is a Turing reduction of A to B that runs in polynomial time. The concept of log-space reduction is similar.

Note that while these reductions are stronger in the sense that they provide a finer distinction into equivalence classes, and have more restrictive requirements than Turing reductions, this is because the reductions themselves are less powerful; there may be no way to build a many-one reduction from one set to another even when a Turing reduction for the same sets exists.