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 f

_{1}, f_{2}, ... be an enumeration of the partial recursive functions. We say f_{i}≠f_{j}if there is some input x such that either- f
_{i}(x) halts and f_{j}(x) does not halt, or - f
_{j}(x) halts and f_{i}(x) does not halt or - both f
_{i}(x) and f_{j}(x) halt and f_{i}(x)≠f_{j}(x).

_{i}≠f_{j}. 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 f_{i}≠^{*}f_{j}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, f_{i}≠^{*}f_{j}.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 questionDoes K Turing reduce to MIN ^{*}?Read Schaefer's paper for details and many more interesting facts about MIN and MIN

^{*}.

--

Posted by Lance Fortnow to My Computational Complexity Web Log at 2/10/2004 06:59:30 PM- f