Skip to main content
1 of 3
Sadeq Dousti
  • 16.6k
  • 9
  • 72
  • 154

This is not a complete answer, yet I think it is helpful.

The answer is in fact taken from the following paper:

Beigel, R. and Goldsmith, J. 1998. Downward Separation Fails Catastrophically for Limited Nondeterminism Classes. SIAM J. Comput. 27, 5 (Oct. 1998), 1420-1429. DOI= http://dx.doi.org/10.1137/S0097539794277421

The abstract states almost everything:

The $\beta$ hierarchy consists of classes $\beta_k={\rm NP}[logkn]\subseteq {\rm NP}$. Unlike collapses in the polynomial hierarchy and the Boolean hierarchy, collapses in the $\beta$ 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 ${\rm P} = \beta_1\subseteq \beta_2\subseteq \cdots \subseteq {\rm NP}$, we can construct an oracle relative to which those collapses and separations hold; at the same time we can make distinct levels of the hierarchy closed under computation or not, as we wish. To give two relatively tame examples: for any $k \geq 1$, we construct an oracle relative to which

$ {\rm P} = \beta_{k} \neq \beta_{k+1} \neq \beta_{k+2} \neq \cdots $

and another oracle relative to which

$ {\rm P} = \beta_{k} \neq \beta_{k+1} = {\rm PSPACE}. $

We also construct an oracle relative to which $\beta_{2k} = \beta_{2k+1} \neq \beta_{2k+2}$ for all k.

This shows that the $\beta$ hierarchy has contradictory relativizations, nominating its separation as a "hard" problem.

The literature does not seem to care much about the $\beta$ hierarchy, since a regular search does not show up with many relevant results. In particular, there's a very limited (and seemingly irrelevant) number of papers citing the above results.

Sadeq Dousti
  • 16.6k
  • 9
  • 72
  • 154