<p>While I don't know a specific (conjectured) example in $QP-\beta P$, there is still rather compelling evidence that $\beta P$ is a <em>proper</em> subset of $QP$. Namely, these classes behave very differently in their relationship to $NP$:</p>

<p>$\bullet$ It is obvious from the definition that $\beta P\subseteq NP$.</p>

<p>$\bullet$ On the other hand, $QP\subseteq NP$ is not known, and it would be very hard to prove, since it implies $P\neq NP$. (In fact, it is an even stronger statement than $P\neq NP$.)</p>

<p>Such a very different behavior relative to $NP$ seems to provide a fairly strong reason to believe that $\beta P\neq QP$.</p>

CC BY-SA 3.0
2017-06-24T08:47:10.223Z
Also, it seems unlikely for $\beta P$ to be closed under complement.
Emil Jeřábek
CC BY-SA 3.0
2017-06-26T06:44:12.893Z
Since, as you mentioned $QP\subseteq NP$ imply $P\neq NP$. As a followup, what would the result of $NP \subseteq QP$ or  $NP \subset QP$ imply in the complexity hierarchy and would it have any impact on $P vs NP$ problem?
TheoryQuest1
CC BY-SA 3.0
2017-06-23T23:57:18.857Z
2017-06-23T23:57:18.857Z
Andras Farago
<p>Yes. We have such problem. It is Graph Isomorphism problem. Babai proved that <a href="https://arxiv.org/abs/1512.03547" rel="nofollow noreferrer">GI is in QP</a>. My understanding is that Babai's proof does not yield limited nondeterminism upper bound ($\beta P$) on the complexity of GI. </p>

<p>We have <a href="https://mathoverflow.net/questions/253518/is-the-graph-isomorphism-problem-in-%CE%B2p-class">no proof that GI is in $\beta P$</a>. Furthermore, we don't have a proof that GI can not be solved using poly-logarithmic nondeterminism. </p>

<p>See this <a href="https://cstheory.stackexchange.com/questions/21930/can-graph-isomorphism-be-decided-with-square-root-bounded-nondeterminism">related post</a>.</p>

<p>This <a href="https://cstheory.stackexchange.com/questions/21930/can-graph-isomorphism-be-decided-with-square-root-bounded-nondeterminism">CS Theory post</a> by @Salamon indicates that we do not even know whether GI can be decided with square-root bounded nondeterminism let alone poly-logarithmic nondeterminism.</p>

CC BY-SA 3.0
2017-06-22T02:47:40.490Z
However, I think many people conjecture that GI is in P.
Thomas Steinke
CC BY-SA 3.0
2017-06-22T02:51:36.780Z
@Thomas Babai in his paper indicated that he is against this conjecture.
Mohammad Al-Turkistany
CC BY-SA 3.0
2017-06-22T23:37:32.217Z
Are you so sure Babai's algorithm isnt in $\beta P$?
Joshua Grochow
CC BY-SA 3.0
2017-06-23T01:35:10.447Z
@JoshuaGrochow As I said in my answer, I don't see how Babai's quasi-polynomial time algorithm would put GI in $\beta P$. Certainly, he did not claim that. Also, see this post on MathOverflow: https://mathoverflow.net/questions/253518/is-the-graph-isomorphism-problem-in-%CE%B2p-class
Mohammad Al-Turkistany
CC BY-SA 3.0
2017-06-23T16:22:26.797Z
@MohammadAl-Turkistany Ironically, the question on MO you cite (both in your answer and your comment) is by the OP himself from 10 months ago, and has no answer (to this day). I am not sure how much this gives credence to your argument -- it only implies that "We have no proof that GI is in $\beta P$ **referenced on MathOverflow**" at best.
Clement C.
CC BY-SA 3.0
2017-06-23T17:09:24.453Z
@ClementC.: While I agree with your reasoning, if you look at my answer [here](https://cstheory.stackexchange.com/a/22059/129) you'll see that I was uncertain as to whether the bounded-degree graph isomorphism test could be done. I had forgotten about that, but I agree that, at least for me, it needs more digging as to whether Babai's algorithm puts GI into $\beta P$.
Joshua Grochow
CC BY-SA 3.0
2017-06-23T17:13:55.120Z
@JoshuaGrochow Yes, the comment is more specific (pointing out the specific part about the degree). But the answer just references the question on MO as what I take as a strong hint for the claim that there is no proof -- which sounds circular to me.
Clement C.
CC BY-SA 3.0
2017-06-22T02:43:44.613Z
2017-06-23T15:20:06.510Z
2017-06-23T15:20:06.510Z
Mohammad Al-Turkistany
<p>Quasi-polynomial time, or QP for short, is a complexity class on deterministic Turing machine. Here is the precise definition:<a href="https://complexityzoo.uwaterloo.ca/Complexity_Zoo:Q#qp" rel="noreferrer">https://complexityzoo.uwaterloo.ca/Complexity_Zoo:Q#qp</a></p>

<p>While βP is a complexity class of limited nondeterminism. Here is the precise definition: <a href="https://complexityzoo.uwaterloo.ca/Complexity_Zoo:B#betap" rel="noreferrer">https://complexityzoo.uwaterloo.ca/Complexity_Zoo:B#betap</a></p>

<p>It is easy to see that any machine of βP can be simulated by a machine of QP, namely, βP $\subseteq$ QP.</p>

<p>But do we have an example, a problem that is in QP but not in βP, even if we just have no precise proof that the problem is not in βP?</p>

<cc.complexity-theory><complexity-classes>
Is there a computing problem which is in quasi-polynomial time but is (maybe) not in $\beta P$?
Arthur Kexu-Wang
# Is there a computing problem which is in quasi-polynomial time but is (maybe) not in $\beta P$?

(Asked by: username_0 on 2017-06-20)

Quasi-polynomial time, or QP for short, is a complexity class on deterministic Turing machine. Here is the precise definition:<https://complexityzoo.uwaterloo.ca/Complexity_Zoo:Q#qp>

While βP is a complexity class of limited nondeterminism. Here is the precise definition: <https://complexityzoo.uwaterloo.ca/Complexity_Zoo:B#betap>

It is easy to see that any machine of βP can be simulated by a machine of QP, namely, βP $\subseteq$ QP.

But do we have an example, a problem that is in QP but not in βP, even if we just have no precise proof that the problem is not in βP?

**Tags:** cc.complexity-theory, complexity-classes

---

## 2 answers

### Answer by username_1 on 2017-06-23. Score: 4

While I don't know a specific (conjectured) example in $QP-\beta P$, there is still rather compelling evidence that $\beta P$ is a *proper* subset of $QP$. Namely, these classes behave very differently in their relationship to $NP$:

$\bullet$ It is obvious from the definition that $\beta P\subseteq NP$.

$\bullet$ On the other hand, $QP\subseteq NP$ is not known, and it would be very hard to prove, since it implies $P\neq NP$. (In fact, it is an even stronger statement than $P\neq NP$.)

Such a very different behavior relative to $NP$ seems to provide a fairly strong reason to believe that $\beta P\neq QP$.

> **Comments:**
> **username_2**: Also, it seems unlikely for $\beta P$ to be closed under complement.  
> **username_3**: Since, as you mentioned $QP\subseteq NP$ imply $P\neq NP$. As a followup, what would the result of $NP \subseteq QP$ or  $NP \subset QP$ imply in the complexity hierarchy and would it have any impact on $P vs NP$ problem?  

---

### Answer by username_4 on 2017-06-22. Score: 3

Yes. We have such problem. It is Graph Isomorphism problem. Babai proved that [GI is in QP](https://arxiv.org/abs/1512.03547). My understanding is that Babai's proof does not yield limited nondeterminism upper bound ($\beta P$) on the complexity of GI.

We have [no proof that GI is in $\beta P$](https://mathoverflow.net/questions/253518/is-the-graph-isomorphism-problem-in-%CE%B2p-class). Furthermore, we don't have a proof that GI can not be solved using poly-logarithmic nondeterminism.

See this [related post](https://cstheory.stackexchange.com/questions/21930/can-graph-isomorphism-be-decided-with-square-root-bounded-nondeterminism).

This [CS Theory post](https://cstheory.stackexchange.com/questions/21930/can-graph-isomorphism-be-decided-with-square-root-bounded-nondeterminism) by @Salamon indicates that we do not even know whether GI can be decided with square-root bounded nondeterminism let alone poly-logarithmic nondeterminism.

> **Comments:**
> **username_5**: However, I think many people conjecture that GI is in P.  
> **username_4**: @Thomas Babai in his paper indicated that he is against this conjecture.  
> **username_6**: Are you so sure Babai's algorithm isnt in $\beta P$?  
> **username_4**: @JoshuaGrochow As I said in my answer, I don't see how Babai's quasi-polynomial time algorithm would put GI in $\beta P$. Certainly, he did not claim that. Also, see this post on MathOverflow: https://mathoverflow.net/questions/253518/is-the-graph-isomorphism-problem-in-%CE%B2p-class  
> **username_7**: @MohammadAl-Turkistany Ironically, the question on MO you cite (both in your answer and your comment) is by the OP himself from 10 months ago, and has no answer (to this day). I am not sure how much this gives credence to your argument -- it only implies that "We have no proof that GI is in $\beta P$ **referenced on MathOverflow**" at best.  
> **username_6**: @ClementC.: While I agree with your reasoning, if you look at my answer [here](https://cstheory.stackexchange.com/a/22059/129) you'll see that I was uncertain as to whether the bounded-degree graph isomorphism test could be done. I had forgotten about that, but I agree that, at least for me, it needs more digging as to whether Babai's algorithm puts GI into $\beta P$.  
> **username_7**: @JoshuaGrochow Yes, the comment is more specific (pointing out the specific part about the degree). But the answer just references the question on MO as what I take as a strong hint for the claim that there is no proof -- which sounds circular to me.  

---

