Reduction

computation

Idea

Idea 1

Assuming that we want to solve a new problem , meaning we want to develop an algorithm for problem . We know how to solve a similar problem , meaning we already have an algorithm for . The idea is to try solve by translating it to , i.e. we develop an algorithm for by using algorithm for .

If this strategy works, we say that problem is reduced to problem , and we write:

Therefore, problem is at least as easy to solve as problem .

Idea 2

Assuming we fail to find a suitable solution method for a new problem , i.e. we find no (efficient) algorithm or not even a semi-decision procedure for problem . We know that a related problem is hard to solve, i.e. it has already been proven that there is no (efficient) algorithm or not even a semi-decision procedure for problem .

Idea: We develop an algorithm for problem that uses a (hypothetical) algorithm for problem .

Constraints

The problem reduction from problem to problem should be easier than the algorithms for and . If would not be the case, then the reduction would reduce a part of the complexity of and a comparison between and would not be possible.

Reductions have to be efficiently solvable, e.g. in polynomial time, i.e. for instances of size and a constant .

Reductions

Turing Reduction

Definition

Turing Reduction

For languages or problems , we say is Turing-reducible to (i.e. ), iff there exists an oracle Turing machine such that for every input :

Here, may take any finite number of (possibly adaptive) membership queries to while computing.

Link to original

Many-One Reduction

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.

Link to original

Karp Reduction

Definition

Karp Reduction

A many-one reduction with a reduction is called Karp reduction if is computable in polynomial time.

Link to original