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$
7
  • 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$ Apr 27, 2017 at 15:39
  • $\begingroup$ @MichaelLampis Yep, if you count the space on the query tape, then that sound right to me! :) $\endgroup$ Apr 27, 2017 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$ Apr 27, 2017 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$ Apr 28, 2017 at 7:10
  • 1
    $\begingroup$ @MarkusBläser I think you should post this as an answer. $\endgroup$ Apr 30, 2017 at 10:45

1 Answer 1

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$
4
  • $\begingroup$ Just to make sure we're on the same page, is it known that $P^{PP} = P^{\#P}$? $\endgroup$ May 1, 2017 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$ May 1, 2017 at 2:27
  • 1
    $\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$ May 1, 2017 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$ May 1, 2017 at 2:35

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.