8
$\begingroup$

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}$?

$\endgroup$
  • 3
    $\begingroup$ 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}$? $\endgroup$ – Michael Lampis Apr 27 '17 at 15:39
  • $\begingroup$ @MichaelLampis Yep, if you count the space on the query tape, then that sound right to me! :) $\endgroup$ – Michael Wehar Apr 27 '17 at 15:55
  • $\begingroup$ 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. :) $\endgroup$ – Michael Wehar Apr 27 '17 at 16:10
  • 5
    $\begingroup$ 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. $\endgroup$ – Markus Bläser Apr 28 '17 at 7:10
  • 1
    $\begingroup$ @MarkusBläser I think you should post this as an answer. $\endgroup$ – Emil Jeřábek Apr 30 '17 at 10:45
6
+50
$\begingroup$

On popular request, here is my comment as an answer:

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.

$\endgroup$
  • $\begingroup$ Just to make sure we're on the same page, is it known that $P^{PP} = P^{\#P}$? $\endgroup$ – Michael Wehar May 1 '17 at 2:26
  • $\begingroup$ 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? $\endgroup$ – Michael Wehar May 1 '17 at 2:27
  • $\begingroup$ Yep, complexity zoo says that they are equal. Also, I think I remember proving this in a complexity theory course a few years ago as an exercise. :) $\endgroup$ – Michael Wehar May 1 '17 at 2:31
  • 2
    $\begingroup$ Complexity zoo also says that my main question is an open problem. Sorry, I didn't realize that. I thought maybe someone out there had solved it. $\endgroup$ – Michael Wehar May 1 '17 at 2:35

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.