# Potentially equal complexity classes without known contradictory relativizations

What are some examples of pairs of complexity classes $A$ and $B$ such that

1. we do not know whether $A=B$, and

2. we do not know contradictory relativizations either (i.e., we do not know oracles $P$ and $Q$ such that $A^P = B^P$ and $A^Q \ne B^Q$)?

To phrase the question another way, what are some exceptions to the heuristic that if can't figure out contradictory relativizations then it is easy to resolve the equality question outright?

• Would any two classes A and B for which we do not know how to prove an oracle separation between A and B suffice to answer your question? (Assuming it is possible for A and B to be equal.) – Robin Kothari Nov 11 '15 at 23:06
• Would you accept examples about implications between equalities, rather than single equalities? For example, we do not know whether NP=UP implies that PH collapses, but we also don't have an oracle in which this implication is false. – Joshua Grochow Nov 11 '15 at 23:21
• @JoshuaGrochow : That is interesting, although I am slightly more interested in the specific type of example I described. – Timothy Chow Nov 12 '15 at 17:28
• @Robin Kothari : If we don't know an oracle Q, then a fortiori we don't know oracles P and Q, so the only way I see for (A,B) to satisfy your requirements but not mine is if we know that A=B but we don't know an oracle that separates them. I guess it might be interesting to see an example of A and B such that A = B yet it's plausible (but not known) that they could be separated by an oracle, but this isn't really what I was asking for. – Timothy Chow Nov 12 '15 at 17:28

I think the biggest such example at present is $BQP$ (quantum polybomial time) vs $PH$ (the polynomial time hierarchy). Significant effort has been put into separating them relative to an oracle, with no success. (Of course a powerful enough oracle will make them equal.) And the best known containment result is that $BQP$ is in $PP$.

Some references for attacks on the oracle problem: http://arxiv.org/abs/0910.4698 http://arxiv.org/abs/1007.0305

• Actually the best known result is $\mathsf{BQP \subseteq AWPP \subseteq PP}$, where $\mathsf{AWPP}$ is (among other things) the largest gap-definable sublcass of $\mathsf{PP}$ such that $\mathsf{PP^{AWPP} = PP}$. I'm not aware of any interest in the class $\mathsf{AWPP}$ apart from its relationship to $\mathsf{BQP}$ and to $\mathsf{PP}$, so as a refinement this is a bit of a technical point, but there you go. – Niel de Beaudrap Nov 12 '15 at 16:34
• Along these lines, it's also not known how to separate BQP from AM, or even QMA from AM. – Robin Kothari Nov 12 '15 at 22:35

Is there an oracle known to separate $\mathsf{P}^{\#\mathsf{P}}$ from $\mathsf{PSPACE}$?

• I'm pretty sure the question was intended more rhetorically, i.e. "I think this is an answer, but maybe there's an oracle known that I'm not aware of" – Joshua Grochow Nov 13 '15 at 4:37
• Yes, thanks Josh. Do you know one? It's very hard to search for, but I recall being unable to learn of one's existence last time I tried. – Ryan O'Donnell Nov 13 '15 at 13:37