Editing Many-one reduction (section)

== Definitions ==

=== Formal languages ===

Suppose <math>A</math> and <math>B</math> are [[formal language]]s over the [[Alphabet (computer science)|alphabets]] <math>\Sigma</math> and <math>\Gamma</math>, respectively. A '''many-one reduction''' from <math>A</math> to <math>B</math> is a [[total computable function]] <math>f: \Sigma^{*}\rightarrow\Gamma^{*}</math> that has the property that each word <math>w</math> is in <math>A</math> if and only if <math>f(w)</math> is in <math>B</math>.

If such a function <math>f</math> exists, one says that <math>A</math> is '''many-one reducible''' or '''m-reducible''' to <math>B</math> and writes
:<math>A \leq_{\mathrm{m}} B.</math>

=== Subsets of natural numbers ===

Given two sets <math>A,B \subseteq \mathbb{N}</math> one says <math>A</math> is '''many-one reducible''' to <math>B</math> and writes
:<math>A \leq_{\mathrm{m}} B</math>
if there exists a [[total computable function]] <math>f</math> with <math>x\in A</math> iff <math>f(x)\in B</math>. 

If the many-one reduction <math>f</math> is [[Injective function|injective]], one speaks of a one-one reduction and writes <math>A \leq_1 B</math>.

If the one-one reduction <math>f</math> is [[Surjective function|surjective]], one says <math>A</math> is '''[[computable isomorphism|recursively isomorphic]]''' to <math>B</math> and writes<ref name="Odifreddi89">[[Piergiorgio Odifreddi|P. Odifreddi]], ''Classical Recursion Theory: The theory of functions and sets of natural numbers'' (p.320). Studies in Logic and the Foundations of Mathematics, vol. 125 (1989), Elsevier 0-444-87295-7.</ref><sup>p.324</sup>
:<math>A\equiv B</math>

=== Many-one equivalence ===

If both <math>A \leq_{\mathrm{m}} B</math> and <math>B \leq_{\mathrm{m}} A</math>, one says <math>A</math> is '''many-one equivalent''' or '''m-equivalent''' to <math>B</math> and writes
:<math>A \equiv_{\mathrm{m}} B.</math>

=== Many-one completeness (m-completeness) ===

A set <math>B</math> is called ''many-one complete'', or simply '''m-complete''', [[iff]] <math>B</math> is recursively enumerable and every recursively enumerable set <math>A</math> is m-reducible to <math>B</math>.