A refinement of the low and high hierarchies

Based on the - and -classes of the polynomial-time hierarchy, Schöning S1], S3]introduced low and high hierarchies within NP Several classes of sets have been located in the bottom few levels of these hierarchies S1], S3], KS], BB], BS2], AH]. Most results placing sets in the -levels of the low hierarchy are related to sparse sets, and the proof techniques employed involve deterministic enumeration of sparse sets. Balcàzaret al. BBS]and Allender and Hemachandra AH] introduced extended low hierarchies, involving sets outside of NP, based on the - and gD-classes of the polynomial-time hierarchy. Several classes of sets have been located in the -levels of these hierarchies as well, and once again most such results involve sparse sets.In this paper we introduce a refinement of the low and high hierarchies and of the extended low hierarchies. Our refinement is based on the -classes of the polynomial-time hierarchy. We show that almost all of the classes of sets that are known to belong to the -levels of the low and extended low hierarchies actually belong to the newly defined -levels of these hierarchies. Our proofs use Kadin's K1]technique of computing the census of a sparse set first, followed by a nondeterministic enumeration of the set. This leads to the sharper lowness results.We also consider the optimality of these new lowness results. For sets in the -levels of the low hierarchy we have oracle results indicating that substantially stronger results are not possible through use of Kadin's technique. For sets in the -classes of the extended low hierarchy we have tight absolute lower bounds; that is, lower bounds without oracles. These bounds are slightly stronger than similar bounds appearing in AH].This work was supported in part by NSF Grant CCR-8909071. The second author's current address is Networking Software Division, IBM Research, Triangle Park, NC 27709, USA.