In computability theory and computational complexity theory, a many-one reduction (also called mapping reduction) is a reduction that converts instances of one decision problem) using a computable function.

Many-one reductions are a special case and stronger form of Turing reductions..

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

Definitions

Formal languages

are formal languages over the alphabets, respectively. A many-one reduction is a total computable function.

is many-one reducible or m-reducible and writes

Subsets of natural numbers

is many-one reducible and writes

if there exists a total computable function.

is injective.

is surjective is recursively isomorphic and writesp.324

Many-one equivalence

is many-one equivalent or m-equivalent and writes

Many-one completeness (m-completeness)

is called many-one complete, or simply m-complete, iff.

Degrees

indeed is an equivalence, its equivalence classes.p.257

Some properties of the m-degrees, some of which differ from analogous properties of Turing degrees:pp.555--581

• There is a well-defined jump operator on the m-degrees.

• The only m-degree with jump 0m is 0m.

• .

• .

• is isomorphic to the theory of second-order arithmetic.

as the unique poset satisfying several explicit properties of its ideals, a similar characterization has eluded the Turing degrees.pp.574--575

Myhill's isomorphism theorem have the same equivalence classes.p.325 are called the 1-degrees.

Many-one reductions with resource limitations

circuits, or polylogarithmic projections where each subsequent reduction notion is weaker than the prior; see polynomial-time reduction and log-space reduction for details.

and an algorithm N 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 outside C to a language in 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 it to a problem in C. 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. It is known for example that the first four listed are closed up to the very weak reduction notion of polylogarithmic time projections. These classes are not closed under arbitrary many-one reductions, however.

Many-one reductions extended

One may also ask about generalized cases of many-one reduction. One such example is e-reduction for e-degrees. The e.

Properties

• The relationss 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 recursively enumerable problems. Thus the halting problem is r.e. complete. Note that it is not the only r.e. complete problem.

• 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.

Karp reductions

A polynomial-time many-one reduction from a problem A to a problem B (both of which are usually required to be decision problems) is a polynomial-time algorithm for transforming inputs to problem A into inputs to problem B, such that the transformed problem has the same output as the original problem. An instance x of problem A can be solved by applying this transformation to produce an instance y of problem B, giving y as the input to an algorithm for problem B, and returning its output. Polynomial-time many-one reductions may also be known as polynomial transformations or Karp reductions, named after Richard Karp.

References