Definition:Mapping Reduction

Definition

Let $\Sigma, \Sigma'$ be finite sets.

Let:

\(\ds L\)

\(\subseteq\)

\(\ds \Sigma^*\)

\(\ds L'\)

\(\subseteq\)

\(\ds \Sigma'^*\)

be sets of finite strings over $\Sigma$ and $\Sigma'$ respectively, where:

$\Sigma^*$ denotes the set of all finite strings over the alphabet $\Sigma$.

Let $f : \Sigma^* \to \Sigma'^*$ be a computable function such that, for all $w \in \Sigma^*$:

$w \in L \iff \map f w \in L'$

Then, $f$ is a mapping reduction from $L$ to $L'$.

If any such $f$ exists, then $L$ is mapping reducible to $L'$, which is denoted as:

$L \le_m L'$

Also known as

The mapping $f$ is frequently called a many-one reduction.

Likewise, $L$ is many-one reducible to $L'$.

Also see

• Results about mapping reductions can be found here.

Sources

• 2013: Michael Sipser: Introduction to the Theory of Computation (3rd ed.): $5.3$ Mapping Reducibility

The validity of the material on this page is questionable. In particular: Is this definition specific to Turing machines? From the way it's worded, it looks as though it ought to be general. You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by resolving the issues. To discuss this page in more detail, feel free to use the talk page. When this work has been completed, you may remove this instance of {{Questionable}} from the code. If you would welcome a second opinion as to whether your work is correct, add a call to {{Proofread}} the page.