Turing Reduction

computation

Definition

Turing Reduction

For languages $A,B\subseteq {\Sigma }^{\ast }$ or problems $A,B$, we say $A$ is Turing-reducible to $B$ (i.e. $A{\le }_{T}B$), iff there exists an oracle Turing machine $M^B$ such that for every input $x$:

$$\forall x:x\in A⟺M^B(x)\text{halts and accepts}$$

Here, $M^B$ may take any finite number of (possibly adaptive) membership queries to $B$ while computing.

Idea

Turing Reduction

A Turing reduction solves a problem $A$ by using a solution procedure for another problem $B$ as a subprocedure. The reduction consists of a control program that may query the subprocedure for instances of $B$ 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

Many-One Reduction

Turing reductions are interactive/algorithmic: an algorithm for $A$ may make multiple, possibly adaptive yes/no queries to $B$.

$$A{\le }_{T}B⟸A{\le }_{m}B$$