Reduction

computation

Idea

Idea 1

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

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

$$A\le B$$

Therefore, problem $A$ is at least as easy to solve as problem $B$.

Idea 2

Assuming we fail to find a suitable solution method for a new problem $B$, i.e. we find no (efficient) algorithm or not even a semi-decision procedure for problem $B$. We know that a related problem $A$ 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 $A$.

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

Constraints

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

Reductions have to be efficiently solvable, e.g. in polynomial time, i.e. $O(n^k)$ for instances of size $n$ and a constant $k\ge 1$.

Reductions

Turing Reduction

Definition

Turing Reduction

For languages $A,B\subseteq {\Sigma }^{\ast }$ or problems $A,B$, we say $A$ is Turing reducible to $B$ (i.e. $A{\le }_{T}B$), iff there exists an oracle Turing machine $M^B$ such that for every input $x$:

$$\forall x:x\in A⟺M^B(x)\text{halts and accepts}$$

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

Link to original

Many-One Reduction

Definition

Many-One Reduction (Language Variant)

For 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).

Many-One Reduction (Problem Variant)

Let $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.

Link to original

Karp Reduction

Definition

Karp Reduction

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

Link to original