Many-one reduction

Suppose A and B are formal languages over the alphabets Σ and Γ, respectively. A many-one reduction from A to B is a total computable function f : Σ^* → Γ^* that has the property that each word w is in A if and only if f(w) is in B.

If such a function f exists, we say that A is many-one reducible or m-reducible to B and write

${\displaystyle A\leq _{\mathrm {m} }B.}$

If there is an injective many-one reduction function then we say A is 1-reducible or one-one reducible to B and write

${\displaystyle A\leq _{1}B.}$

Given two sets ${\displaystyle A,B\subseteq \mathbb {N} }$ we say ${\displaystyle A}$ is many-one reducible to ${\displaystyle B}$ and write

${\displaystyle A\leq _{\mathrm {m} }B}$

if there exists a total computable function ${\displaystyle f}$ with ${\displaystyle A=f^{-1}(B).}$ If additionally ${\displaystyle f}$ is injective we say ${\displaystyle A}$ is 1-reducible to ${\displaystyle B}$ and write

${\displaystyle A\leq _{1}B.}$

If ${\displaystyle A\leq _{\mathrm {m} }B\,\mathrm {and} \,B\leq _{\mathrm {m} }A}$ we say ${\displaystyle A}$ is many-one equivalent or m-equivalent to ${\displaystyle B}$ and write

${\displaystyle A\equiv _{\mathrm {m} }B.}$

If ${\displaystyle A\leq _{1}B\,\mathrm {and} \,B\leq _{1}A}$ we say ${\displaystyle A}$ is 1-equivalent to ${\displaystyle B}$ and write

${\displaystyle A\equiv _{1}B.}$

A set B is called many-one complete, or simply m-complete, iff B is recursively enumerable and every recursively enumerable set A is m-reducible to B.