# Does there exist an oracle $A$ such that $(P^{\#P})^{A} \neq PSPACE^{A}$?

Background

We know that $P^{\#P} \subseteq PSPACE$.

In addition, we known from Toda's theorem that $PH \subseteq P^{\#P}$.

For more background on $\#P$, see here: https://en.wikipedia.org/wiki/Sharp-P

Question

Does there exist an oracle $A$ such that $(P^{\#P})^{A} \neq PSPACE^{A}$?

• I would guess that for the first part, setting $A=\textrm{PSPACE}$ should be enough, right? Isn't it true that $\textrm{PSPACE}^{\textrm{PSPACE}} = \textrm{PSPACE}$? Commented Apr 27, 2017 at 15:39
• @MichaelLampis Yep, if you count the space on the query tape, then that sound right to me! :) Commented Apr 27, 2017 at 15:55
• Great, thank you very much for pointing that out! I modified the question removing the easier part about finding an oracle where they are equal. :) Commented Apr 27, 2017 at 16:10
• There is an oracle separating PP from PSPACE: Jacobo Toran, A combinatorial technique for separating counting complexity classes, ICALP 1989. The best result for P^PP that I know is a conditional result by Heribert Vollmer: Relating polynomial time to constant depth. TCS, 207: 159-170, 1998. Commented Apr 28, 2017 at 7:10
• @MarkusBläser I think you should post this as an answer. Commented Apr 30, 2017 at 10:45

There is an oracle separating $\mathrm{PP}$ from $\mathrm{PSPACE}$: Jacobo Toran, A combinatorial technique for separating counting complexity classes, ICALP 1989. The best result for $\mathrm{P}^\mathrm{PP}$ that I know is a conditional result by Heribert Vollmer: Relating polynomial time to constant depth. TCS, 207: 159-170, 1998.
• Just to make sure we're on the same page, is it known that $P^{PP} = P^{\#P}$? Commented May 1, 2017 at 2:26
• It seems straight forward that $P^{PP} \subseteq P^{\#P}$, but the other direction seems a little tricky. You do some sort of binary search to compute the number of solutions to a verifier? Commented May 1, 2017 at 2:27