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

CC BY-SA 3.0
2015-11-13T04:37:46.487Z
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
CC BY-SA 3.0
2015-11-13T13:37:20.113Z
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
CC BY-SA 3.0
2015-11-12T21:21:14.700Z
2015-11-12T21:21:14.700Z
Ryan O'Donnell
<p>I think the biggest such example at present is $BQP $ (quantum polybomial time) vs $PH $ (the polynomial time hierarchy). <strong>Significant</strong> 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 $. </p>

<p>Some references for attacks on the oracle problem:
<a href="http://arxiv.org/abs/0910.4698">http://arxiv.org/abs/0910.4698</a>
<a href="http://arxiv.org/abs/1007.0305">http://arxiv.org/abs/1007.0305</a></p>

CC BY-SA 3.0
2015-11-12T16:34:49.223Z
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
CC BY-SA 3.0
2015-11-12T22:35:32.157Z
Along these lines, it's also not known how to separate BQP from AM, or even QMA from AM.
Robin Kothari
CC BY-SA 3.0
2015-11-12T02:53:03.497Z
2015-11-12T02:53:03.497Z
Ryan Williams
<p>What are some examples of pairs of complexity classes $A$ and $B$ such that</p>

<ol>
<li><p>we do not know whether $A=B$, and</p></li>
<li><p>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$)?</p></li>
</ol>

<p>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?</p>

CC BY-SA 3.0
2015-11-11T23:06:27.757Z
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
CC BY-SA 3.0
2015-11-11T23:21:46.123Z
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
CC BY-SA 3.0
2015-11-12T17:28:44.250Z
@JoshuaGrochow : That is interesting, although I am slightly more interested in the specific type of example I described.
Timothy Chow
CC BY-SA 3.0
2015-11-12T17:28:57.530Z
@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
<cc.complexity-theory><complexity-classes><relativization>
Potentially equal complexity classes without known contradictory relativizations
Timothy Chow
# Potentially equal complexity classes without known contradictory relativizations

(Asked by: username_0 on 2015-11-11)

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?

**Tags:** cc.complexity-theory, complexity-classes, relativization

> **Comments:**
> **username_1**: 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.)  
> **username_2**: 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.  
> **username_0**: @JoshuaGrochow : That is interesting, although I am slightly more interested in the specific type of example I described.  
> **username_0**: @username_1 : 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.  

---

## 2 answers

### Answer by username_4 on 2015-11-12. Score: 17 | Accepted answer

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>

> **Comments:**
> **username_5**: 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.  
> **username_1**: Along these lines, it's also not known how to separate BQP from AM, or even QMA from AM.  

---

### Answer by username_3 on 2015-11-12. Score: 5

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

> **Comments:**
> **username_2**: 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"  
> **username_3**: 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.  

---

