information:extraction
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.

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 {\displaystyle B} if there is a Turing reduction of A {\displaystyle A} to B {\displaystyle B} that runs in polynomial time. The concept of log-space reduction is similar.

These reductions are stronger in the sense that they provide a finer distinction into equivalence classes, and satisfy more restrictive requirements than Turing reductions. Consequently, such reductions are harder to find. 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.