Tuesday, February 10, 2004

Minimal Indices

Let's look at some interesting questions about the set of smallest programs. This post relates more to recursion theory than complexity theory. No time bounds today.

Let f1, f2, ... be an enumeration of the partial recursive functions. We say fi≠fj if there is some input x such that either

  1. fi(x) halts and fj(x) does not halt, or
  2. fj(x) halts and fi(x) does not halt or
  3. both fi(x) and fj(x) halt and fi(x)≠fj(x).
Define the set MIN as the set of indices i such that for all j<i, fi≠fj. How hard is the set MIN?

MIN is in Σ2 of the arithmetic hierarchy. For all j<i you need to check that for some input x, one of the three conditions above hold (which might require a ∀ to check that a machine does not halt). We have two unbounded quantifiers (the first "for all" is bounded) so MIN is in Σ2.

In fact this is tight for Turing reductions, every problem in Σ2 reduces to MIN.

For an interesting open question we turn to a variation called MIN*. We say fi*fj if one of the three conditions above hold for infinitely many x. MIN* contains the set of indices i such that for all j<i, fi*fj.

Without too much effort one can show MIN* is in Π3. Marcus Schaefer shows that every language in Π3 can be Turing reduces to an oracle that encodes both MIN* and K where K is the usual halting problem. We would like to remove K which is equivalent to the following open question

Does K Turing reduce to MIN*?

Read Schaefer's paper for details and many more interesting facts about MIN and MIN*.

No comments:

Post a Comment