<p>This is not a complete answer, yet I think it is helpful.</p>
<p>The answer is in fact taken from the following paper:</p>
<p>Beigel, R. and Goldsmith, J. 1998. Downward Separation Fails Catastrophically for Limited Nondeterminism Classes. <em>SIAM J. Comput.</em> 27, 5 (Oct. 1998), 1420-1429. DOI= <a href="http://dx.doi.org/10.1137/S0097539794277421" rel="nofollow noreferrer">http://dx.doi.org/10.1137/S0097539794277421</a></p>
<p>The abstract states almost everything:</p>
<blockquote>
<p>The <span class="math-container">$\beta$</span> hierarchy consists of classes <span class="math-container">$\beta_k={\rm NP}[\log^k n]\subseteq {\rm NP}$</span>. Unlike collapses in the polynomial hierarchy and the Boolean hierarchy, collapses in the <span class="math-container">$\beta$</span> 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 <span class="math-container">${\rm P} = \beta_1\subseteq \beta_2\subseteq \cdots \subseteq {\rm NP}$</span>, 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 <span class="math-container">$k \geq 1$</span>, we construct an oracle relative to which</p>
<p><span class="math-container">$ {\rm P} = \beta_{k} \neq \beta_{k+1} \neq \beta_{k+2} \neq \cdots $</span></p>
<p>and another oracle relative to which</p>
<p><span class="math-container">$ {\rm P} = \beta_{k} \neq \beta_{k+1} = {\rm PSPACE}. $</span></p>
<p>We also construct an oracle relative to which <span class="math-container">$\beta_{2k} = \beta_{2k+1} \neq \beta_{2k+2}$</span> for all k.</p>
</blockquote>
<p>This shows that the <span class="math-container">$\beta$</span> hierarchy has contradictory relativizations, nominating its separation as a &quot;hard&quot; problem.</p>
<p>The literature does not seem to care much about the <span class="math-container">$\beta$</span> 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 <a href="http://scholar.google.com/scholar?cites=6683854578350522992&amp;as_sdt=2005&amp;sciodt=2000&amp;hl=en" rel="nofollow noreferrer">papers citing the above results</a>.</p>
<hr />
<h3>Unrelated but Worth Noting</h3>
<p>You may also see:</p>
<p><code>The complexity of optimization problems. Journal of Computer and System Sciences, 36:490-509, 1988.</code></p>
<p>where it's proved that If <span class="math-container">$FP^{NP} = FP^{NP[log]}$</span> (that is, allowed only a logarithmic number of queries), then <span class="math-container">$P = NP$</span>.</p>

CC BY-SA 2.5
2010-09-27T20:21:34.710Z
2010-09-29T07:49:56.843Z
2020-06-17T09:38:08.363Z
Sadeq Dousti
<p>For attempts to separate the bounded nondeterminism hierarchy, I think monotone dualization of prime formulas is the most salient topic.</p>

<p>Consider the decision problem</p>

<blockquote>
  <p><strong>MONOTONE DUAL</strong><br>
  <em>Input:</em> two monotone CNF formulas, from which no literals can be removed<br>
  <em>Question:</em> is the one formula the dual of the other?</p>
</blockquote>

<p>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.  </p>

<p>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.</p>

<p>This is surveyed in:</p>

<ul>
<li>Thomas Eiter, Kazuhisa Makino, and Georg Gottlob, <em>Computational aspects of monotone dualization: A brief survey</em>, DAM <strong>156</strong> 2035– 2049, 2008.  doi: <a href="http://dx.doi.org/10.1016/j.dam.2007.04.017">10.1016/j.dam.2007.04.017</a> (<a href="http://www.kr.tuwien.ac.at/research/reports/rr0601.pdf">preprint</a>)</li>
</ul>

<p>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.</p>

CC BY-SA 2.5
2010-09-26T17:35:13.247Z
2010-09-27T21:28:42.497Z
2010-09-27T21:28:42.497Z
András Salamon
<p>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>

<p>$P=\beta_1P$. Notice that <a href="https://cstheory.stackexchange.com/questions/609/what-are-the-best-known-upper-bounds-and-lower-bounds-for-computing-olog-n-cliq">$O(\log n)$-clique</a>
<a href="https://cstheory.stackexchange.com/questions/609/what-are-the-best-known-upper-bounds-and-lower-bounds-for-computing-olog-n-cliq"></a> 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$</p>

<blockquote>
  <p>What is the most serious attempt at separating  $\beta_1P$ from $\beta_2P$?</p>
</blockquote>

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

<p>This reference contains a survey of limited nondeterminism:</p>

<p><a href="http://archive.uky.edu/bitstream/10225/212/levythes.pdf" rel="nofollow noreferrer">A SURVEY OF LIMITED NONDETERMINISM
IN COMPUTATIONAL COMPLEXITY THEORY</a>
<a href="http://archive.uky.edu/bitstream/10225/212/levythes.pdf" rel="nofollow noreferrer"></a></p>

CC BY-SA 2.5
2010-09-26T08:03:56.000Z
I'll refer you to the meta discussion on [how to ask a question](http://meta.cstheory.stackexchange.com/questions/300/how-to-ask-a-good-question), and in particular the part about explaining why YOU care.
Suresh Venkat
CC BY-SA 2.5
2010-09-26T13:29:34.350Z
@Suresh, for me, the $\beta_1P$ vs. $\beta_2P$ problem looks more natural problem than the $P$ vs $NP$ problem.
Mohammad Al-Turkistany
CC BY-SA 2.5
2010-09-26T14:56:50.030Z
Yes, but can you summarize what's known first and any conjectures/questions you might have ?
Suresh Venkat
CC BY-SA 2.5
2010-09-26T15:35:12.520Z
Does $\beta_k P=NP(\log^k n)$ define an infinite hierarchy?
Mohammad Al-Turkistany
CC BY-SA 2.5
2010-09-26T15:49:51.110Z
Then the question should be that: it's better to ask more focused questions. Also, please fix the typos in the title
Suresh Venkat
CC BY-SA 2.5
2010-09-26T16:05:28.940Z
For random in place of non-deterministic bits, see http://eccc.hpi-web.de/report/2009/039/.
Kaveh
<cc.complexity-theory><nondeterminism>
Separation of limited nondeterminism classes?
Mohammad Al-Turkistany
# Separation of limited nondeterminism classes?

(Asked by: username_0 on 2010-09-26)

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](https://cstheory.stackexchange.com/questions/609/what-are-the-best-known-upper-bounds-and-lower-bounds-for-computing-olog-n-cliq)
 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](http://archive.uky.edu/bitstream/10225/212/levythes.pdf)

**Tags:** cc.complexity-theory, nondeterminism
> **Comments:**
> **username_1**: I'll refer you to the meta discussion on [how to ask a question](http://meta.cstheory.stackexchange.com/questions/300/how-to-ask-a-good-question), and in particular the part about explaining why YOU care.  
> **username_0**: @Suresh, for me, the $\beta_1P$ vs. $\beta_2P$ problem looks more natural problem than the $P$ vs $NP$ problem.  
> **username_1**: Yes, but can you summarize what's known first and any conjectures/questions you might have ?  
> **username_0**: Does $\beta_k P=NP(\log^k n)$ define an infinite hierarchy?  
> **username_1**: Then the question should be that: it's better to ask more focused questions. Also, please fix the typos in the title  
> **username_2**: For random in place of non-deterministic bits, see http://eccc.hpi-web.de/report/2009/039/.  

---

## 2 answers

### Answer by username_4 on 2010-09-26. Score: 7 | Accepted answer

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](http://dx.doi.org/10.1016/j.dam.2007.04.017) ([preprint](http://www.kr.tuwien.ac.at/research/reports/rr0601.pdf))

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 by username_3 on 2010-09-27. Score: 6

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](http://scholar.google.com/scholar?cites=6683854578350522992&as_sdt=2005&sciodt=2000&hl=en).

---

### 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$.


---

