Definition
Turing Reduction
For languages
or problems , we say is Turing-reducible to (i.e. ), iff there exists an oracle Turing machine such that for every input : Here,
may take any finite number of (possibly adaptive) membership queries to while computing.
Idea
Turing Reduction
A Turing reduction solves a problem
by using a solution procedure for another problem as a subprocedure. The reduction consists of a control program that may query the subprocedure for instances of arbitrarily often. The control program itself must still be an algorithm. If the reduction is restricted to polynomial time, then it is called a Cook reduction.
Difference to Many-One Reduction
Turing reductions are interactive/algorithmic: an algorithm for