Downward Separation Fails Catastrophically for Limited Nondeterminism Classes

Title: Downward Separation Fails Catastrophically for Limited Nondeterminism Classes

Authors: Richard Beigel and Judy Goldsmith

Abstract: The β hierarchy consists of sets β_k = NP[log^kn] ⊆ NP. Unlike collapses in the polynomial hierarchy and the Boolean hierarchy, collapses in the β hierarchy do not seem to translate up, nor does closure under complement seem to cause the hierarchy to collapse. For any consistent set of collapses and separations of levels of the hierarchy that respects P = β₁ ⊆ β₂ ⊆ ... ⊆ NP, we can construct an oracle relative to which those collapses and separations hold, yet any (or all) of the β_k's are closed under complement. To give two relatively tame examples: For any k ≥ 1, we construct an oracle relative to which

P = β_k ≠ β_k+1 ≠ β_k+2 ≠ ... and another oracle relative to which P = β_k ≠ β_k+1 = PSPACE. We also construct an oracle relative to which β_2k = β_2k+1 ≠ β_2k+2 for all k.

Download Full Paper