Many-one Reduction

computation

Definition

Many-One Reduction

Language Variant

For languages or problems , we say many-one reduces to (i.e. ) iff there exists a computable total function such that for all :

The function is the reduction (mapping).

Problem Variant

Let be a function from the set of instances of problem to a set of instances of problem , i.e.:

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

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

Idea

Many-One Reduction

A many-one reduction maps every instance of a problem to an instance of a problem . Solving already gives the correct answer for .

For decision problems, this means that is a positive instance of if and only if is a positive instance of .

The mapping 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 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 does not have to be bijective. In particular, it need not be injective and it need not be surjective.

Several different instances of problem may be mapped to the same instance of problem .

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

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

Difference to Turing Reduction

Turing Reduction

Many-one reductions are functional translations: one computable map with . One “single-shot” encoding.

Transfer of Decidability

If , then algorithmic properties transfer in the following direction:

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

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

Transfer of Complexity

If , then complexity-theoretic properties transfer as follows:

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

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