チューリング還元
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 formula_2 if there is a Turing reduction of formula_1 to formula_2 that runs in polynomial time. The concept of log-space reduction is similar.