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

Improve this question
$\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$
    – Michael Lampis
    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$
    – Michael Wehar
    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$
    – Michael Wehar
    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$
    – Markus Bläser
    Apr 28, 2017 at 7:10
  • 1
    $\begingroup$ @MarkusBläser I think you should post this as an answer. $\endgroup$
    – Emil Jeřábek
    Apr 30, 2017 at 10:45

1 Answer 1

Reset to default
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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.