Many-One Reduction

computation

Definition

Many-One Reduction (Language Variant)

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

Many-One Reduction (Problem Variant)

Let $R$ be a function from the set $I_A$ of instances of problem $A$ to a set $I_B$ of instances of problem $B$, i.e.:

$$R:I_A\to I_B$$

If we solve $R(x)$ for with a decider for problem $B$, then the result for instance $R(x)$ already provides the correct result for instance $x$ of problem $A$. If so, $x$ and $R(x)$ are called equivalent. For decision problems $A$ and $B$, it means that $x$ is a positive instance of $A$ iff $R(x)$ is a positive instance of $B$

$$x\in I_A^{+}⟺R(x)\in I_B^{+}$$

The function $R$ must be (efficiently) computable. In the case of a resource constrained on polynomial time, then $R$ is called Karp reduction.

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