A REFINEMENT OF THE LOW AND HIGH HIERARCHIES

Based on the Sigma- and Delta-classes of the polynomial-time hierarchy , Schoning [S1], [S3] introduced low and high hierarchies within NP. S everal classes of sets have been located in the bottom few levels of t hese hierarchies [S1], [S3], [KS], [BB], [BS2], [AH]. Most results pla cing sets in the Delta-levels of the low hierarchy are related to spar se sets, and the proof techniques employed involve deterministic enume ration of sparse sets. Balcazar et al. [BBS] and Allender and Hemachan dra [AH] introduced extended low hierarchies, involving sets outside o f NP, based on the Sigma- and Delta-classes of the polynomial-time hie rarchy. Several classes of sets have been located in the Delta-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 h igh hierarchies and of the extended low hierarchies. Our refinement is based on the Theta-classes of the polynomial-time hierarchy. We show that almost all of the classes of sets that are known to belong to the Delta-levels of the low and extended low hierarchies actually belong to the newly defined Theta-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 Theta-leveIs 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 Th eta-classes of the extended low hierarchy we have tight absolute lower bounds; that is, lower bounds without oracles. These bounds are sligh tly stronger than similar bounds appearing in [AH].