Category:Definitions/Mapping Reductions

This category contains definitions related to Mapping Reductions.
Related results can be found in Category:Mapping Reductions.

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

Let:

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