9

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?

Mohammad Al-Turkistany
  • 20,928
  • 5
  • 63
  • 149
Arthur Kexu-Wang
  • 91
  • 4
  • 4
    Let f be the number_of_states_ function, and consider the problem $\hspace{2.36 in}$ "Does M halt in at most (f(M))$^{\hspace{.02 in}\log(\hspace{.04 in}f(M))}$ steps?" . ​ ​ ​ ​ –  Jun 21 '17 at 06:34

2 Answers2

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

Andras Farago
  • 11,396
  • 37
  • 70
  • 2
    Also, it seems unlikely for $\beta P$ to be closed under complement. – Emil Jeřábek Jun 24 '17 at 08:47
  • 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 Jun 26 '17 at 06:44
3

Yes. We have such problem. It is Graph Isomorphism problem. Babai proved that GI is in QP. 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$. Furthermore, we don't have a proof that GI can not be solved using poly-logarithmic nondeterminism.

See this related post.

This CS Theory post by @Salamon indicates that we do not even know whether GI can be decided with square-root bounded nondeterminism let alone poly-logarithmic nondeterminism.

Mohammad Al-Turkistany
  • 20,928
  • 5
  • 63
  • 149
  • 1
    However, I think many people conjecture that GI is in P. – Thomas Jun 22 '17 at 02:47
  • 1
    @Thomas Babai in his paper indicated that he is against this conjecture. – Mohammad Al-Turkistany Jun 22 '17 at 02:51
  • 2
    Are you so sure Babai's algorithm isnt in $\beta P$? – Joshua Grochow Jun 22 '17 at 23:37
  • @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 Jun 23 '17 at 01:35
  • 1
    @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. Jun 23 '17 at 16:22
  • @ClementC.: While I agree with your reasoning, if you look at my answer here 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 Jun 23 '17 at 17:09
  • 1
    @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. Jun 23 '17 at 17:13