← •   HOME  • UP  •   →
Top/Reduction/Mapping reductions  

6.2. Mapping Reductions


The definition of a mapping reduction

Mapping reductions are used to reduce one decision problem to another decision problem.

Suppose that A and B are two languages (sets of strings).

Definition. A mapping reduction from A to B is a computable function f such that, for every string x,

x ∈ A ⇔ f(x) ∈ B.

Definition. Say that A ≤ m B if a mapping reduction from A to B exists.

For example, suppose that

A = {x | x is an even integer}
B = {x | x is an odd integer}
Then function f(x) = x + 1 is a mapping reduction from A to B. Notice that

x ∈ A ⇔ x is even
  ⇔ x + 1 is odd
  ⇔ x + 1 ∈ B
  ⇔ f(x) ∈ B

Mapping reductions imply Turing reductions

Suppose that that f is a mapping reduction from A to B. Then we can define a Turing reduction from A to B as follows. 

   is x ∈ A?
   y = f(x)
   If y ∈ B then
     answer yes
   else
     answer no
   end if

Inspecting that Turing reduction, you can see that a mapping reduction amounts to a special case of a Turing reduction where

  1. You can only use the oracle once.
  2. You must stop immediately after getting the answer from the oracle, and your answer must be the same as the oracle's answer.

In practice, most Turing reductions between languages can be expressed as mapping reductions, or at least can be converted into mapping reductions.

Mapping reductions have the advantage that they are a little easier to describe. They also have other advantages that we see later.


The fundamental theorem of mapping reducibility

Since a mapping reduction can be turned into a Turing reduction, we immediately get the following theorems about mapping reductions from the fundamental theorem of Turing reductions, which can be expressed in two equivalent ways.

Theorem. If B is computable and A ≤ m B then A is computable.

Theorem. If A is uncomputable and A ≤ m B then B is uncomputable.


Transitivity

Like Turing reducibility, mapping reducibility is transitive.

Theorem. If A ≤ m B and B ≤ m C then A ≤ m C.

Proof. Suppose that f is a mapping reduction from A to B and g is a mapping reduction from B to C. So f and g are computable, and

(1) x ∈ A ⇔ f(x) ∈ B
(2) x ∈ B ⇔ g(x) ∈ C

Then h(x) = g(f(x)) is a mapping reduction from A to C. Certainly, h is computable, since both f and g are computable. Also,

x ∈ A ⇔ f(x) ∈ B  by (1)
  ⇔ g(f(x)) ∈ C  by (2)
  ⇔ h(x) ∈ C

So h satisfies the requirements of a mapping reduction from A to C. ◊

 

← •   HOME  • UP  •   →
Top/Reduction/Mapping reductions