Many-One Reduction

computation

Definition

Many-One Reduction

Language Variant languages $A,B\subseteq {\Sigma }^{\ast }$ or problems $A,B$, we say $A$ many-one reduces to $B$ (i.e. $A{\le }_{m}B$) iff there exists a computable total function $f:{\Sigma }^{\ast }\to {\Sigma }^{\ast }$ such that for all $x$:

$$\forall x:x\in A⟺f(x)\in B$$

The function $f$ is the reduction (mapping).

Problem Variant $R$ be a function from the set $I_A$ of instances of problem $A$ to a set $I_B$ of instances of problem $B$, i.e.:

$$R:I_A\to I_B$$

If we solve $R(x)$ for with a decider for problem $B$, then the result for instance $R(x)$ already provides the correct result for instance $x$ of problem $A$. If so, $x$ and $R(x)$ are called equivalent. For decision problems $A$ and $B$, it means that $x$ is a positive instance of $A$ iff $R(x)$ is a positive instance of $B$

$$x\in I_A^{+}⟺R(x)\in I_B^{+}$$

The function $R$ must be (efficiently) computable. In the case of a resource constrained on polynomial time, then $R$ is called Karp reduction.

Idea

Many-One Reduction

A many-one reduction maps every instance $x$ of a problem $A$ to an instance $R(x)$ of a problem $B$. Solving $R(x)$ already gives the correct answer for $x$.

For decision problems, this means that $x$ is a positive instance of $A$ if and only if $R(x)$ is a positive instance of $B$.

The mapping $R$ must be efficiently computable. If it is restricted to polynomial time, then it is called a Karp reduction.

Many-one reductions are a special case of Turing reductions: the subprocedure for $B$ is called exactly once, and the computation ends immediately afterwards.

In this sense, a many-one reduction is side-effectless.

Non-Bijectivity

The reduction map $R$ does not have to be bijective. In particular, it need not be injective and it need not be surjective.

Several different instances $x_1,x_2,\dots$ of problem $A$ may be mapped to the same instance $R(x)$ of problem $B$.

This is why the reduction is called a many-one reduction: potentially, many source instances can have the same image under $R$.

The only essential requirement is that the map is a correct many-one reduction, i.e. a correct reduction:

$$x\in I_A^{+}⟺R(x)\in I_B^{+}$$

Difference to Turing Reduction

Turing Reduction

Many-one reductions are functional translations: one computable map $f$ with $x\in A⟺f(x)\in B$. One “single-shot” encoding.

$$A{\le }_{m}B⟹A{\le }_{T}B$$

Transfer of Decidability

If $A{\le }_{m}B$, then algorithmic properties transfer in the following direction:

• if $B$ is decidable, then $A$ is decidable;
• if $B$ is semi-decidable, then $A$ is semi-decidable;
• if $A$ is not semi-decidable, then $B$ is not semi-decidable;
• if $A$ is undecidable, then $B$ is undecidable.

In general, positive decidability properties transfer backwards from $B$ to $A$, while negative properties transfer forwards from $A$ to $B$.

Transfer of Complexity

If $A{\le }_{P}B$, then complexity-theoretic properties transfer as follows:

• if $B$ is in P, then $A$ is in P;
• if $B$ is in NP, then $A$ is in NP;
• if $A$ is NP-hard, then $B$ is NP-hard;
• if $A$ is NP-complete and $B$ is in NP, then $B$ is NP-complete.

Thus, membership in P and NP transfers backwards along a reduction, while NP-hardness transfers forwards.