Reduction

computation

Reductions

Turing Reduction

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.

Link to original

Many-One Reduction

Definition

Many-One Reduction

For languages $A,B\subseteq {\Sigma }^{\ast }$ or problems $A,B$, we say $A$ many-one reduces to $B$ (i.e. $A{\le }_{m}B$) iff there exists a computable total function $f:{\Sigma }^{\ast }\to {\Sigma }^{\ast }$ such that for all $x$:

$$\forall x:x\in A⟺f(x)\in B$$

The function $f$ is the reduction (mapping).

Link to original