# What is different between two classes are 'incomparable' or two classes are 'not equal'?

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'?

• 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$. Commented Jun 20, 2022 at 7:32

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