Many-one reduction

In computability theory and computational complexity theory, a many-one reduction is a reduction which converts instances of one decision problem into instances of a second decision problem. Reductions are thus used to measure the relative computational difficulty of two problems.

Many-one reductions are a special case and stronger form of Turing reductions. With many-one reductions the oracle can be invoked only once at the end and the answer cannot be modified.

Many-one reductions were first used by Emil Post in a paper published in 1944.^[1] Later Norman Shapiro used the same concept in 1956 under the name strong reducibility.

Definitions

Formal languages

Suppose A and B are formal languages over the alphabets Σ and Γ, respectively. A many-one reduction from A to B is a total computable function f : Σ^* → Γ^* that has the property that each word w is in A if and only if f(w) is in B (that is, $A = f^{-1}(B)$).

If such a function f exists, we say that A is many-one reducible or m-reducible to B and write

$A \leq_{\mathrm{m}} B.$

If there is an injective many-one reduction function then we say A is 1 reducible or one-one reducible to B and write

$A \leq_1 B.$

Subsets of natural numbers

Given two sets $A,B \subseteq \mathbb{N}$ we say $A$ is many-one reducible to $B$ and write

$A \leq_{\mathrm{m}} B$

if there exists a total computable function $f$ with $A = f^{-1}(B).$ If additionally $f$ is injective we say $A$ is 1-reducible to $B$ and write

$A \leq_1 B.$

Many-one equivalence and 1 equivalence

If $A \leq_{\mathrm{m}} B \, \mathrm{and} \, B \leq_{\mathrm{m}} A$ we say $A$ is many-one equivalent or m-equivalent to $B$ and write

$A \equiv_{\mathrm{m}} B.$

If $A \leq_1 B \, \mathrm{and} \, B \leq_1 A$ we say $A$ is 1-equivalent to $B$ and write

$A \equiv_1 B.$

Many-one completeness (m-completeness)

A set B is called many-one complete, or simply m-complete, iff B is recursively enumerable and every recursively enumerable set A is m-reducible to B.

Many-one reductions with resource limitations

Many-one reductions are often subjected to resource restrictions, for example that the reduction function is computable in polynomial time or logarithmic space; see polynomial-time reduction and log-space reduction for details.

Given decision problems A and B and an algorithm N which solves instances of B, we can use a many-one reduction from A to B to solve instances of A in:

• the time needed for N plus the time needed for the reduction
• the maximum of the space needed for N and the space needed for the reduction

We say that a class C of languages (or a subset of the power set of the natural numbers) is closed under many-one reducibility if there exists no reduction from a language in C to a language outside C. If a class is closed under many-one reducibility, then many-one reduction can be used to show that a problem is in C by reducing a problem in C to it. Many-one reductions are valuable because most well-studied complexity classes are closed under some type of many-one reducibility, including P, NP, L, NL, co-NP, PSPACE, EXP, and many others. These classes are not closed under arbitrary many-one reductions, however.

Properties

• The relations of many-one reducibility and 1 reducibility are transitive and reflexive and thus induce a preorder on the powerset of the natural numbers.
• $A \leq_{\mathrm{m}} B$ if and only if $\mathbb{N} \setminus A \leq_{\mathrm{m}} \mathbb{N} \setminus B.$
• A set is many-one reducible to the halting problem if and only if it is recursively enumerable. This says that with regards to many-one reducibility, the halting problem is the most complicated of all computer programs. Thus the halting problem is many-one complete.
• The specialized halting problem for an individual Turing machine T (i.e., the set of inputs for which T eventually halts) is many-one complete iff T is a universal Turing machine. Emil Post showed that there exist recursively enumerable sets that are neither decidable nor m-complete, and hence that there exist nonuniversal Turing machines whose individual halting problems are nevertheless undecidable.

References

1. E. L. Post, "Recursively enumerable sets of positive integers and their decision problems", Bulletin of the American Mathematical Society 50 (1944) 284-316

Reading

• E. L. Post, "Recursively enumerable sets of positive integers and their decision problems", Bulletin of the American Mathematical Society 50 (1944) 284-316
• Norman Shapiro, "Degrees of Computability", Transactions of the American Mathematical Society 82, (1956) 281-299