Many-One Reduction

computation

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).

Difference to Turing Reduction

Many-one reductions are functional translations: one computable map $f$ with $x\in A⟺f(x)\in B$. One “single-shot” encoding.

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