ISSN:
1433-0490
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
Notes:
Abstract 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].
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01185399
Permalink
