Separation of limited nondeterminism classes?

Question

It is interesting to find the best lower bound on the number of nondeterministic bits needed to solve satisfiability problem. Let $\beta_k P$ be the class of problems solvable by a nondeterministic Turing machine in polynomial time and using $O(\log^k n)$ nondeterministic bits.

$P=\beta_1P$. Notice that $O(\log n)$-clique is in $\beta_2P$. It is an open problem whether $\beta_1 P = \beta_2 P$. It is known that $\beta_1P \neq \beta_2P$ implies $P \neq NP$

What is the most serious attempt at separating $\beta_1P$ from $\beta_2P$?

Does $\beta_kP=NP(\log^k n)$ form an infinite hierarchy?

This reference contains a survey of limited nondeterminism:

A SURVEY OF LIMITED NONDETERMINISM IN COMPUTATIONAL COMPLEXITY THEORY

Answer 1

For attempts to separate the bounded nondeterminism hierarchy, I think monotone dualization of prime formulas is the most salient topic.

Consider the decision problem

MONOTONE DUAL
Input: two monotone CNF formulas, from which no literals can be removed
Question: is the one formula the dual of the other?

MONOTONE DUAL can be decided with $O((\log\ n)^2/\log\ \log\ n)$ nondeterministic steps. There is also a quasi-polynomial $n^{o(\log\ n)}$ time upper bound for this problem which has stood since 1996.

So MONOTONE DUAL is in co-$\beta_2$P and also doesn't seem to require the full power of this class. On the other hand, MONOTONE DUAL may be a good candidate for a problem that is outside P = co-$\beta_1$P.

This is surveyed in:

• Thomas Eiter, Kazuhisa Makino, and Georg Gottlob, Computational aspects of monotone dualization: A brief survey, DAM 156 2035– 2049, 2008. doi: 10.1016/j.dam.2007.04.017 (preprint)

I am not sure there is more work along these lines. As with many other areas with the potential to separate P from NP, after some promising early progress new ideas now appear to be necessary.

Answer 2

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}[\log^k n]\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.

---

Unrelated but Worth Noting

You may also see:

The complexity of optimization problems. Journal of Computer and System Sciences, 36:490-509, 1988.

where it's proved that If $FP^{NP} = FP^{NP[log]}$ (that is, allowed only a logarithmic number of queries), then $P = NP$.