15
$\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?

Improve this question
$\endgroup$
4
  • 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
    Commented Nov 11, 2015 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
    Commented Nov 11, 2015 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
    Commented Nov 12, 2015 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
    Commented Nov 12, 2015 at 17:28

2 Answers 2

Reset to default
17
$\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

Improve this answer
$\endgroup$
2
  • 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
    Commented Nov 12, 2015 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
    Commented Nov 12, 2015 at 22:35
5
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • 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
    Commented Nov 13, 2015 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
    Commented Nov 13, 2015 at 13:37

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.