16
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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.) $\endgroup$ – Robin Kothari Nov 11 '15 at 23:06
  • 2
    $\begingroup$ 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. $\endgroup$ – Joshua Grochow Nov 11 '15 at 23:21
  • $\begingroup$ @JoshuaGrochow : That is interesting, although I am slightly more interested in the specific type of example I described. $\endgroup$ – Timothy Chow Nov 12 '15 at 17:28
  • $\begingroup$ @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. $\endgroup$ – Timothy Chow Nov 12 '15 at 17:28
18
$\begingroup$

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

$\endgroup$
  • 3
    $\begingroup$ 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. $\endgroup$ – Niel de Beaudrap Nov 12 '15 at 16:34
  • 2
    $\begingroup$ Along these lines, it's also not known how to separate BQP from AM, or even QMA from AM. $\endgroup$ – Robin Kothari Nov 12 '15 at 22:35
5
$\begingroup$

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

$\endgroup$
  • 6
    $\begingroup$ 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" $\endgroup$ – Joshua Grochow Nov 13 '15 at 4:37
  • 1
    $\begingroup$ 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. $\endgroup$ – Ryan O'Donnell Nov 13 '15 at 13:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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