Many-one reduction

Incomputability theoryandcomputational complexity theory,amany-one reduction(also calledmapping reduction) is areductionthat converts instances of onedecision problem(whether an instance is in$L_{1}$) to another decision problem (whether an instance is in$L_{2}$) using acomputable function.The reduced instance is in the language$L_{2}$if and only if the initial instance is in its language$L_{1}$.Thus if we can decide whether$L_{2}$instances are in the language$L_{2}$,we can decide whether$L_{1}$instances are in its language by applying the reduction and solving for$L_{2}$.Thus, reductions can be used to measure the relative computational difficulty of two problems. It is said that$L_{1}$reduces to$L_{2}$if, in layman's terms$L_{2}$is at least as hard to solve as$L_{1}$.This means that any algorithm that solves$L_{2}$can also be used as part of a (otherwise relatively simple) program that solves$L_{1}$.

Many-one reductions are a special case and stronger form ofTuring reductions.With many-one reductions, the oracle (that is, our solution for$L_{2}$) can be invoked only once at the end, and the answer cannot be modified. This means that if we want to show that problem$L_{1}$can be reduced to problem$L_{2}$,we can use our solution for$L_{2}$only once in our solution for$L_{1}$,unlike in Turing reductions, where we can use our solution for$L_{2}$as many times as needed in order to solve the membership problem for the given instance of$L_{1}$.

Many-one reductions were first used byEmil Postin a paper published in 1944.LaterNorman Shapiroused the same concept in 1956 under the namestrong reducibility.

Definitions

Formal languages

Suppose$A$and$B$areformal languagesover theAlpha bets$\Sigma$and$\Gamma$,respectively. Amany-one reductionfrom$A$to$B$is atotal computable function$f:\Sigma ^{*}\rightarrow \Gamma ^{*}$that has the property that each word$w$is in$A$if and only if$f(w)$is in$B$.

If such a function$f$exists, one says that$A$ismany-one reducibleorm-reducibleto$B$and writes

$A\leq _{\mathrm {m} }B.$

Subsets of natural numbers

Given two sets$A,B\subseteq \mathbb {N}$one says$A$ismany-one reducibleto$B$and writes

$A\leq _{\mathrm {m} }B$

if there exists atotal computable function$f$with$x\in A$iff$f(x)\in B$.

If the many-one reduction$f$isinjective,one speaks of a one-one reduction and writes$A\leq _{1}B$.

If the one-one reduction$f$issurjective,one says$A$isrecursively isomorphicto$B$and writes^p.324

$A\equiv B$

Many-one equivalence

If both$A\leq _{\mathrm {m} }B$and$B\leq _{\mathrm {m} }A$,one says$A$ismany-one equivalentorm-equivalentto$B$and writes

$A\equiv _{\mathrm {m} }B.$

Many-one completeness (m-completeness)

A set$B$is calledmany-one complete,or simplym-complete,iff$B$is recursively enumerable and every recursively enumerable set$A$is m-reducible to$B$.

Degrees

The relation$\equiv _{m}$indeed is anequivalence,itsequivalence classesare called m-degrees and form a poset${\mathcal {D}}_{m}$with the order induced by$\leq _{m}$.^p.257

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

• There is a well-defined jump operator on the m-degrees.
• The only m-degree with jump0_m′ is0_m.
• There are m-degrees$\mathbf {a} >_{m}{\boldsymbol {0}}_{m}'$where there does not exist$\mathbf {b}$where$\mathbf {b} '=\mathbf {a}$.
• Every countable linear order with a least element embeds into${\mathcal {D}}_{m}$.
• The first order theory of${\mathcal {D}}_{m}$is isomorphic to the theory of second-order arithmetic.

There is a characterization of${\mathcal {D}}_{m}$as the unique poset satisfying several explicit properties of itsideals,a similar characterization has eluded the Turing degrees.^pp.574--575

Myhill's isomorphism theoremcan be stated as follows: "For all sets$A,B$of natural numbers,$A\equiv B\iff A\equiv _{1}B$."As a corollary,$\equiv$and$\equiv _{1}$have the same equivalence classes.^p.325The equivalences classes of$\equiv _{1}$are called the1-degrees.

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, logarithmic space, by$AC_{0}$or$NC_{0}$circuits, or polylogarithmic projections where each subsequent reduction notion is weaker than the prior; seepolynomial-time reductionandlog-space reductionfor details.

Given decision problems$A$and$B$and analgorithmNthat solves instances of$B$,we can use a many-one reduction from$A$to$B$to solve instances of$A$in:

• the time needed forNplus the time needed for the reduction
• the maximum of the space needed forNand the space needed for the reduction

We say that a classCof languages (or a subset of thepower setof the natural numbers) isclosed under many-one reducibilityif there exists no reduction from a language outsideCto a language inC.If a class is closed under many-one reducibility, then many-one reduction can be used to show that a problem is inCby reducing it to a problem inC.Many-one reductions are valuable because most well-studied complexity classes are closed under some type of many-one reducibility, includingP,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 ise-reduction,where we consider$f:A\to B$that are recursively enumerable instead of restricting to recursive$f$.The resulting reducibility relation is denoted$\leq _{e}$,and its poset has been studied in a similar vein to that of the Turing degrees. For example, there is a jump set${\boldsymbol {0}}_{e}^{'}$fore-degrees. Thee-degrees do admit some properties differing from those of the poset of Turing degrees, e.g. an embedding of the diamond graph into the degrees below${\boldsymbol {'}}_{e}$.

Properties

• Therelationsof many-one reducibility and 1-reducibility aretransitiveandreflexiveand thus induce apreorderon thepowersetof 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 thehalting problemif and only ifit isrecursively 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 anindividualTuring machineT(i.e., the set of inputs for whichTeventually halts) is many-one complete iffTis auniversal Turing machine.Emil Post showed that there exist recursively enumerable sets that are neitherdecidablenor m-complete, and hence thatthere existnonuniversal Turing machines whose individual halting problems are nevertheless undecidable.

Karp reductions

Apolynomial-timemany-one reduction from a problemAto a problemB(both of which are usually required to bedecision problems) is a polynomial-time algorithm for transforming inputs to problemAinto inputs to problemB,such that the transformed problem has the same output as the original problem. An instancexof problemAcan be solved by applying this transformation to produce an instanceyof problemB,givingyas the input to an algorithm for problemB,and returning its output. Polynomial-time many-one reductions may also be known aspolynomial transformationsorKarp reductions,named afterRichard Karp.A reduction of this type is denoted by$A\leq _{m}^{P}B$or$A\leq _{p}B$.