display | more...

Many-one reducibility formalizes the common procedure in formal language theory and the theory of computation of reducing one problem to another to show that a particular theorem applies to them both. In symbols, we say two sets A and B are many-one reducible by saying A ≤M B. This means that there must exist some total recursive function f:A → B such that if x is in A if and only if f(x) is in B. This relation is clearly reflexive (a set is obviously many-one reducible to itself) and transitive (by composing the total recursive functions together), but not symmetric (as an inverse for f might not in general exist).

Many theorems exist that use many-one reduction as a key element. For instance, if we have some set A that is many-one reducible to a recursive set, then A must itself be recursive. Similarly if A ≤M B, with B being a recursively enumerable set, then A must also be r.e. This is very useful in proving certain sets decidable or undecidable.

This notion is extended in complexity theory with the idea of polynomial time many-one reducibility. It is the same as plain many-one reducibility, with the additional restriction that the total recursive function in the definition must be computable by some deterministic Turing machine that runs in polynomial time. This idea plays a key role in the theory of NP-complete problems, as it figures prominently in the formal definition of NP-completeness. A formal language/problem is said to be NP-complete if it is in NP and also is polynomial-time many-one reducible to any other problem in NP (that is it is NP-hard).

Log in or register to write something here or to contact authors.