Category:Mapping Reductions

This category contains results about Mapping Reductions.
Definitions specific to this category can be found in Definitions/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'$.