8.  Many-one Reduction

Reduction is one of the most central concepts of the theory of computability.  Informally, problem X reduces problem Y just in case there exists a way to transform an arbitrary solution to X into a solution to Y.  This doesn't imply that Y has a solution to be converted into a solution to X, so reducibility concerns a mathematically counterfactual world in which chickens have lips and cows can fly.

Why visit that world?  Reduction is important because it allows us to turn solutions to one problem into solutions to another and also to turn a proof of unsolvability for one problem into a proof that another problem is unsolvable.  Thus, we can greatly increase our stock of demonstrably solvable and unsolvable problems.

So far, our only example of an unsolvable problem is the halting problem.  The proof was by a reinterpretation of Cantor's diagonal argument.  This worked because the halting problem is simplly concocted to be the diagonal of the characterisic matrix of the r.e. sets.  But using the halting problem as a "seed", we can use reduction to obtain lots of other unsolvable problems.

Reducibility may also be thought of as a qualitative ordering of relative "difficulty" among problems.  If the solution to one problem implies a solution to another, then the former problem is no easier than the latter, for it is impossible for former to have a solution when the latter does not.

We may then ask whether there exists a problem in a complexity class that is as hard as all the problems in the class.  Such problems are said to be complete.  A solution of such a problem can be turned, via reductions, into solutions for all the problems in the class.  Thus, such a solution may be thought of as "canonical" for the class.

Definitions

Many-one reducibility is defined as follows:
X £mY Û ($ total recursive g. "x, X(x) Û Y(g(x))).
Then we say that Y many-one reduces X, or that X is many-one reducible to Y.  The definition says that the total function g projects X into Y and ØX into ØY.  Use of the ordering notation invites us to prove that such notation is justified:

Proposition 1:
£m is a pre-order (reflexive and transitive).
X £mY Û ØX £m ØY

Exercise 1:  Prove it.
-|

Symmetrizing a pre-order always yields a natural concept of equivalence:

X ºmYÛ X £mY Ù Y £mX.
This is called many-one equivalence.  Equvalence relations allow us to define equivalence classes called many-one degrees.
[X]m = {Y Í N: X ºmY }.
Another mathematical instinct is to use the original pre-order to define a partial order over degrees:
[X]m £m [Y]mÛX£mY.
But this expression doesn't amount to a relation on degrees unless we show that the relation doesn't depend on the chosen representatives.  Then one must show that £m is indeed a partial order over degrees.  I assume you have done this already in a discrete math class.  If you haven't, verify it for yourself now.

Now let G Í Pow(N).  Then define

X is G-hard Û "YÎ G, Y £m X.
X is G-complete ÛYÎ G Ù  X is G-hard.

R.e. Completeness

Recall that a set X is complete in a complexity class just in case X is in the class and each member of the class reduces to X. It turns out that K is r.e. complete.  Thus, K is "king of the hill" in r.e. land.

Proposition 6:  K is r.e. complete.

Proof:  We need to reduce each r.e. set to K.  Suppose S is r.e., so for for some k, S = W[k].  Define

y(x, y) » mz U(k, d(z, 0), d(z, 1), <x>)  » f[k](x).
Choose an index and apply s-m-n to obtain total recursive g such that:
f[g(x)](y) »y(x, y).
Thus,
S(x) Û
W[k](x) Û
f[k](x)¯ Û
y(x, g(x))¯ Û
f[g(x)](g(x))¯ Û
K(g(x)).
-|

Preservation Results

The main applications of reducibility are consequences of the elementary but important fact that recursive enumerability and recursiveness are preserved downward in the many-one ordering.  The idea is that the reduction is a "preprocessor" that "converts" the new problem X into inputs for the problem Y in such a way that the solution to Y is converted into a solution to X.

Proposition 2:

  1. X £mY Ù Y is r.e.Þ X is r.e.
  2. X £mY Ù Y is recursive Þ X is recursive.


Proof:  Suppose X£mY.  Then

$ total recursive g. "x, X(x) Û Y(g(x)).
Suppose Y is recursive.  Then Y(x) is a recursive function of x.  So X(x) = Y(g(x)) is a recursive function of x.  So X is recursive.
Suppose Y is r.e.  So for some n,  Y = W[n] = dom(f[n]).  The composition C(f[n], g) is also partial recursive.  We have
C(f[n], g)(x)¯Ûf[n](g(x))¯ Û Y(g(x))  Û X(x).
Thus, X = dom(C(f[n], g)), so X is r.e.
-|

Examples

Now we may use this result to show that lots of new problems are unsolvable, using K and ØK as "seeds".  For example, consider the following, elementary input-output properties of partial recursive indices. In general, let GÍ Part be given.  Define
index(G) = {n ÎN: f[n] ÎG}.
Now say that X is an index set just in case there exists a GÍ Part such that X = index(G).  All the above are index sets.

Exercise 2:   Is K an index set?

Proposition 3:
K £mZd, ØUnd, Tot, ØTot, Inf, ØInf, Onto, ØOnto.
ØK£m ØZd, Und, Tot, ØTot, Inf, ØInf, Onto, ØOnto.

Proof: The second statement follows from the first by proposition 1.

For the first statement, the idea is to produce a very informative reduction.  It suffices to construct a g that projects everything in K to one function and everything in ØK to another.  Thus, one g could serve to reduce many different problems.  For example, we an construct a g such that g(x) is an index of the identity function p1,1 if K(x) and such that g(x) is an index of the everywhere undefined function Æ otherwise.  This g reduces K to Zd, ØUnd, Tot, Inf, Onto, all at once!

Since we are trying to construct a total recurisive function of indices, you will expect that we will use the universal construction together with the s-m-n  theorem to construct the reduction.   Using the universal construction, define the partial recursive function:

y(x, y) » y + o(mzU(x, d(z, 0), d(z, 1), <x>)).
 Choosing an index k for y and applying the s-m-n theorem, we obtain a total recursive g such that:
f[g(x)](y) »f[s(k, x)](y) »f[k, 2](x, y) »y(x, y) » y + o(mzU(x, d(z, 0), d(z, 1), <x>)).
Thus,
K(x) Þ f[g(x)] = p1,1;
ØK(x) Þ f[g(x)] = Æ.
The total recursive g witnesses,
K £mZd, ØUnd, Tot, Inf, Onto.
To reduce K to ØTot, ØInf, ØOnto, we need a different kind of strategy.  The preceding construction went "with the grain", halting just in case a given index halts on itself.  This time, we have to produce a function that does a lot of halting when a given index does not halt on itself.  This sounds suspicious.  Doesn't it require "seeing the future" to be sure when to halt?  No.  For we can effectively halt on a given input when the given index does not halt on itself in a given amount of time depending on that input.  Define
y(x, y) » y + o(mzØU(x, y, d(z, 1), <x>)).
Choosing an index k for y and applying the s-m-n theorem, we obtain a total recursive g such that:
f[g(x)](y) »f[s(k, x)](y) »f[k, 2](x, y) »y(x, y) » y + o(mzØU(x, y, d(z, 1), <x>)).
Observe that if K(x), then for some k, for all y ³k, mzØU(x, y, d(z, 1), <x>)­.  Thus,
ØK(x) Þf[g(x)] = p1,1;
K(x) Þ dom(f[g(x)]) is finite.
So g witnesses:
K £m ØTot, ØInf, ØOnto.
-|

Corollary 4:
ØZd, Und, Tot, ØTot, Inf, ØInf, Onto, ØOnto are not r.e.
Zd, ØZd, Und, ØUnd, Tot, ØTot, Inf, ØInf, Onto, ØOnto are not recursive.

Proof:  Propositions 2, 3.
-|

Rice's Theorem

(Rogers exercise 5-29)
In the preceding result,  none of the index sets in question turned out to be recursive.  In fact,
no nontrivial index set is recursive.
That means that
a compiler cannot reliably check for any input-output property of the program being compiled.
The following proposition establishes these facts.  To facilitate the statement of the theorem, say that a set is nontrivial just in case it is neither N nor Æ.

Proposition 5 (Rice's theorem):  No nontrivial index set is recursive.

Proof:  The trick is that we can effectively act like the everywhere undefined function if x doesn't halt on itself and act like an arbitrary partial recursive function d otherwise.
Let G be a nontrivial subset of Part.
Case I:  suppose Æ Î G.
Then since G is nontrivial, there exists some d Î Part - G.  Now construct:

y(x, y) » d(y) + o(mzU(x, d(z, 0), d(z, 1), <x>)).
By using s-m-n  in the usual way, construct total recursive g such that
f[g(x)](y) » d(y) + o(mzU(x, d(z, 0), d(z, 1), <x>)).
Thus,
K(x) Þ f[g(x)] = d Ï G;
ØK(x) Þ f[g(x)] = Æ Î G.
So   ØK £mindex(G).  Thus, index(G) is not r.e. and hence is not recursive.
Case II:  suppose Æ Ï G.  Then since G is nontrivial, there exists some d Î Part - G.
So the same reduction g establishes that K £mindex(G), so Øindex(G) is not r.e. and hence index(G)  is not recursive.
-|

The Rice-Shapiro Theorem

(Rogers Exercise 5.37)
There are no interesting recursive index sets.  But there are clearly interesting r.e. index sets; ØUnd, for example (do you see why this is r.e.?)  Can we obtain a nice, general characterization of the r.e. index sets?  Yes!  And the result is very interesting from an epistemological point of view.  We need a couple of natural concepts to do so.  Let q be a partial recursive function.  Define
[q] = {y Î Part: q Í y}.
That is, [q] denotes the set of all partial recursive functions that extend [q].
Say that
G is experimentally verifiable Û there exists a collection D of finite functions such that G = Èq ÎD[q].
Why do I call this "experimental verifiability"?  Well, suppose that G is experimentally verifiable in the sense just defined.  Suppose you  investigate whether x Î index(G) by treating x as a black box and simulating index x in a dovetail construction to discover more and more values of f[x] through time.  Then whenever you observe that the data points I have received extend some q Î D, you know that the function you are experimentally studying is in G, becaue every extension of a finite function in D is in G.  Conversely, if the data never extend a finite function in D, then the function you are studying is not in  G, so you are correct for never declaring with certainty that the function you are studying is in G.

The following result provides a more logically explicit way of looking at experimental verifiability.

Lemma 6: G is experimentally verifiable Û ("y Î Part, y Î GÛ $ finite q Í y, q ÎG).

Proof:  Suppose G is experimentally verifiable.
Thus, there exists a collection D of finite functions such that G = Èq ÎD[q].
Let y Î Part be given.
Suppose that y Î G.
Then for some finite q Î D, y Î [q].
Since y Î [q], we have q Í y.
Since [q] Í G, we have q ÎG.
Conversely, suppose $ finite q Í y, q ÎG.
So for some t Î D, q Î[t] Í G. .
So t Í q Í y.
So y Î[t] Í G.

For the converse of the lemma, suppose that "y Î Part, y ÎGÛ $ finite q Í y, q ÎG.
For each y Î G, choose such a qy.
Define D = {qy: y ÎG}.
Since each y ÎG is included in [qy], we have:  G Í Èq ÎD[q].
Also, [qy] Í G  by choice of qy, so Èq ÎD[q] Í G.
Thus, G = Èq ÎD[q].
-|

The following result says that if formal methods can verify a property of input-output behavior by peering at the programs, then an ideal agent would have been able to verify the input-output property from experimental evidence derived from studying the program as a black box on various inputs for various amounts of runtime.  This is an amazing fact.  A priori, one would expect to do a lot better by looking at code than by simply doing behavioral experiments.  Properties that are not experimentally verifiable are exactly the properties that pose Hume's problem of inductive skepticism.  Thus, we see that some index sets are not formally verifiable because of empirical skepticism. This seems to cut to the heart of the traditional empiricist distinction between relations of ideas and matters of fact.  The idea was that relations of ideas are relatively unproblematic since the mind has complete control of the ideas "all at once", whereas empirical truth always outruns our observations.  The following result shows that the same is actually true in formal reasoning by computational means.

Proposition 7:
G is not experimentally verifiable Þ ØK £m index(G). Hence:
 index(G) is r.e. Þ G is experimentally verifiable

Proof:  Suppose that G is not experimentally verifiable. Then by the preceding lemma,

Ø("y Î Part, y Î GÛ $ finite q Í y, q ÎG).
Driving the negation in yields $y Î Part such that:
Case I:  y ÎG Ù " finite q Í y.q ÏG or
Case II: y ÏG Ù $ finite q Í y, q ÎG.
Case I:  Consider the situation.  Some y Î G has the unfortunate property that each finite evidence sequence drawn experimentally from y
is the complete evidence for a non-member of G.  That's just the problem of induction, which tells us that empirical verifiability is impossible.  Now we are going to make the problem of induction into a problem for formal program verification.  That is, we are going to cross the  philosophical boundary betwen matters of fact and relations of ideas!

In particular, we are going to reduce ØK to index(G).  So

given an index x such that ØK(x), we want to produce an index that acts like y, and
given an index x such that K(x), we want to produce an index that acs like some finite subfunction of y.
Intuitively, we can do this by means of a universal construction that simulates f[x](x) for longer and longer runtimes waiting to see it halt.  As more and more time passes, the construction produce more and more of the outputs specified by y, so that if f[x](x) never halts, we produce all of y.  On the other hand, if f[x](x) halts, we use this as a signal to stop making new outputs, so we end up producing some finite subfunction of y.  Notice that his reduction "goes against the grain", turning halting into non-halting (check the example above to see how to set up such a construction).

Case II:  In this situation, there is a function ynot in G such that some finite subfunction q of y is in G.  Again, we wish to reduce ØK to index(G).  We can do this by a universal construction that pretends to be  until f[x](x) halts and that starts making outputs from y thereafter.

Exercise 3:  Finish cases I and II.  Hint:  follow the intuitive motivation, inspect the reductions inolved in proposition 3, and give proper constructions using the universal and s-m-n theorems.
-|
Exercise 4:  Use lemma 6 and proposition 7  to show that the set of all indices of functions with values never exceeding k is not r.e. If you feel shaky, try a few of the problems mentioned in corollary 4.

Experimental verifiability is only a necessary condition for recursive enumerability of an index set.

Exerise 4 (optional):  Find a counterexample to the converse of proposition 6.  Hint: Make the property "empirically" easy to decide but make it computationally as hard as ØK to "interpret" the readily available data.

That is because the "verifying data sequences" in D might not be effectively enumerable.  To overcome this, we can effectively encode finite functions as numbers and then require that the set of code numbers be r.e.  There are many ways to effectively code finite functions.  One such way is to define an indexing q[0], q[1], ...,  q[n],... of the unary, finite functions as follows: (Rogers, section 5.6):

q[n](x) = mz £ n $w£ n(<x, z> = d(n, w)).
In other words, n results from applying the following procedure to finite function q:
  1. Code the ordered pairs in the function by the binary encoding.
  2. Choose some finite enumeration of the resulting code numbers.
  3. Gödel number this sequence.
  4. According to our numbering, the Gödel number easily exceeds the length of the sequence and each item occurring in the sequence, so the search bounds are respected.
Such indices may be called ff indices, for "finite function."

It is possible to move effectively from finite indices to partial recursive indices, but not conversely.  The intuitive idea behind this is that one can decide which pairs are in a finite function from its ff index but not from an arbitrary partial recursive index.

Proposition 8:

  1. $ total recursive g "n, q[n] = f[g(n)].
  2. Ø$ total recursive g "n, f[n] is finite Þ q[g(n)] = f[n].
Proof:  For part 1, we need to turn a finite function index into a standard index.  It doesn't matter which standard index we choose.  Here's a handy way to do it.  The following function is partial recursive:
y(n, x) » mz $w £ lh(z) (<x, z> = d(n, w)).
So it has an index k.
f[k](n, x) » y(n, x).
In the proof of the s-m-n theorem, you constructed a function h such that
f[h(n)] = cn.
Observe that for a given n,
q[n](x) »
mz $w £ lh(z) (<x, z> = d(n, w)) »
mz $w £ lh(z) (<x, z> = d(cn(x), w)) »
y(cn(x), x) »
f[k](cn(x), x) »
C(f[k], cn)(x) »
f[<k, <h(n)>](x).
Hence, the desired, total recursive g is:
g(n) = <k, <h(n)>>.
For part 2, suppose there exists such a total recursive g.  Observe that there is at most one ff index for the everywhere undefined function Æ, namely, 0, the Gödel number of the empty sequence.  So g witnesses:
Null  £m {0}.
But {0} is recursive, contradicting propositions 2 and 3.
-|

Given a set D of finite functions, define

ff-index(D) = {n: q[n] Î D}.
Define:
G is effectively experimentally verifiable just in case there exists a collection D of finite functions such that
  1. ff-index(D) is r.e. and
  2. G = Èq ÎD[q].
Now we can state an exact characterization of the r.e. index sets in terms of effective experimental verification.  So formal program verification is essentially the same as effective empirical program verification.

Proposition 9:  index(G) is r.e. Û G is effectively experimentally verifiable.

So we may choose k so that ff-index(D) = W[k].
To verify index(G), we use a dovetail construction to check whether the given index extends some finite function in D.
We can verify this because we can decide which pairs are in a finite function from ff indices.
That is the whole point of introducing ff indices.
Define

y(n) »mz "w£ lh (d(z, 0)), U(n, d(z, 1), d(d(d(z, 0), w), 0), <d(d(d(z, 0), w), 1)>).
This construction seeks pairs <i, j>, where i is a runtime bound and j is viewed as an ff-index.
Then by the definition of the ff indexing, d(d(d(z, 0), w), 0) denotes an element of the domain of q[j] and d(d(d(z, 0), w), 0) denotes the corresponding value of q[j].
So on input n,  the construction simply searches for an ff index j such that q[j] Í f[n].
There is such a j just in case
f[n] ÎÈq ÎD[q] = G.
So we have a partial recursive y such that index(G) = dom(y).

Conversely, suppose that index(G) is r.e.  We need to construct a collection of finite functions such that ff-index(D)is r.e.
So let index(G) = W[n].
Then by proposition 7 and  lemma 6 we have

(*) "y Î Part, y ÎG Û $ finite q Í y, q ÎG.
Let total recursive g translate ff indices into partial recursive indices as promised by proposition 8.  Define:
D = {q[k]: W[n](g(k))}.
Now define
y(k) » f[n](g(k)).
Evidently,
ff-index(D) = dom(y),
so ff-index(D) is r.e.
Since index(G) = W[n], we have D Í G.
By (*), we have that each y ÎG extends some element of D.
Thus G = Èq ÎD[q].
So G is effectively experimentally verifiable.
-|