# 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, ).

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

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

### Subsets of natural numbers

Given two sets we say is **many-one reducible** to and write

if there exists a total computable function with
If additionally is injective we say is **1-reducible** to and write

### Many-one equivalence and 1 equivalence

If
we say is **many-one equivalent** or **m-equivalent** to and write

If
we say is **1-equivalent** to and write

### 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.
- if and only if
- 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*.__non__universal Turing machines whose individual halting problems are nevertheless undecidable

## References

- ↑ 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