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.

Difference to 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$$