1
$\begingroup$

Arora and Barak states (p. 230) the following:

What is the relation between $BQP$ and $NP$? It seems that quantum computers only offer a quadratic speedup (using Grover’s search) on $NP$-complete problems. There are also oracle results showing that $NP$ problems require exponential time on quantum computers [BBBV97]. So most researchers believe that $NP \subsetneq BPP$. On the other hand, there is a problem in $BQP$ (the Recursive Fourier Sampling or RFS problem [BV93]) that is not known to be in the polynomial-hierarchy, let alone in $NP$. Thus it seems that BQP and NP may be incomparable classes.

My question is: what is different between two classes are 'incomparable' or two classes are 'not equal'?

I knew that it is possible that $P \neq NP$, but $P \subsetneq NP$, so classes P and NP are comparable. Also, I am aware that when two classes have different type then they are incomparable, e.g. one is decision problems (NP) and another is counting problems (#P), then they are not comparable. But BQP and NP are both decision class of problems, so it is not clear to me why Arora and Barak said that both classes could be incomparable. For example, why not saying they are 'not equal' instead of 'incomparable'?

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ Here $A$ and $B$ are incomparable just means that neither $A \subseteq B$ nor $B \subseteq A$. This is stronger than saying $A \neq B$ since, for example, $P \neq EXPTIME$ but $P \subseteq EXPTIME$. $\endgroup$
    – Steven
    Commented Jun 20, 2022 at 7:32

1 Answer 1

Reset to default
1
$\begingroup$

Two sets $A$ and $B$ are comparable if $A \subseteq B$ or $B \subseteq A$. However, if $A \neq B$, it could be that $A \subsetneq B$ or $B \subsetneq A$.

If $A \neq B$ and $A$ and $B$ are comparable, we know that (wlog) all elements of $A$ also are in $B$, and this is an interesting piece of information.

If $A$ and $B$ are incomparable they are necessarily not equal ($A \neq B$). It also means that there is an element in $A$ that is not in $B$, and an element in $B$ that is not in $A$.

For example, since $P \subseteq NP$, we know that every problem in $P$ has a polynomial-time verification since every fact about problems in $NP$ is also true about problems in $P$.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thank you! it is clear now! $\endgroup$
    – user777
    Commented Jun 20, 2022 at 7:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.