SELF-P-PRINTABILITY AND POLYNOMIAL-TIME TURING EQUIVALENCE TO A TALLY SET

The class of self-P-printable sets, those sets that are enumerable in polynomial time relative to themselves, has been shown to be the same as the class of sets that have small generalized Kolmogorov complexity relative to themselves [J. Hartmanis and L. Hemachandra, Proc. 3rd Annual Symposium on Theoretical Aspects of Computer Science, Springer-Verlag, Berlin, New York, 1986, pp. 321-333] and [J. Balcazar and R. Book, Acta Informatica, 23 (1986), pp. 679-688]. This class properly includes the sets of small generalized Kolmogorov complexity, including the tally sets. The class of sets polynomial time Turing equivalent to a tally set includes the class of self-P-printable sets [J. Balcazar and R. Book, op. cit.], and the inclusion is clearly proper because every self-P-printable set must be sparse while there are many nonsparse sets (such as all nonsparse sets in P) that are polynomial time Turing equivalent to a tally set. The question of whether or not the class of self-P-printable sets is the same as the class of sparse sets that are polynomial time Turing equivalent to a tally set is addressed here. Necessary and sufficient conditions for the equivalence of these two classes are presented. Also presented are relativizations for all possible combinations of these necessary and sufficient conditions, suggesting that the nonrelativized solution to the question of this equivalence will be difficult to determine.