Foundations of ComplexityLesson 5: Reductions

Previous Lesson | Next Lesson

In the previous lesson we gave examples of two noncomputable sets. The set

L_A = { <M> | Machine M does accept input <M>} is computably enumerable but not computable while the set L_D = { <M> | Machine M does not accept input <M>} is not even computably enumerable.

We also defined computable functions. In this lesson we will use computable functions to create other languages that are not computable. To do so we use the notion of reduction. Informally a reduction takes one decision problem and reduces it to another problems. For example to know your current longitude, you only need to know the time of day in a fixed location. The problem of computing the longitude reduces to the problem of proper time-keeping. This is one way the longitude issue was dealt with before the days of GPS.

Formally we say a language A reduces to language B if there is a computable function f such that for all x in Σ^*, x is in A if and only if f(x) is in B.

The power of reductions come from the following lemma.

Lemma: Let A and B be sets such that A is reducible to B.

1. If B is computable then A is computable.
2. If B is computably enumerable then A is computably enumerable.
3. If A is not computable then B is not computable.
4. If A is not computably enumerable then B is not computably enumerable.

Lines 1 and 2 are easy to see: Just compute f(x) and simulate the program for B on f(x). Lines 3 and 4 are just the contrapositive of 1 and 2 and turn out to be especially useful.

For example, consider the universal Turing machine language,

L_U = { (<M>,x) | Machine M does accept input x} We have seen L_U is computably enumerable. Let f(<M>)=(<M>,<M>). The function f is easily seen to be computable and reduces L_A to L_U. Thus by our Lemma, line 3, we have that L_U is not computable.

Reductions play a major role in computational complexity so it is very instructive to see them in this context. Next lesson we will use more complicated reductions to show other simple languages are not computable.