<p>On popular request, here is my comment as an answer:</p>

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

CC BY-SA 3.0
2017-05-01T02:26:10.780Z
Just to make sure we're on the same page, is it known that $P^{PP} = P^{\#P}$?
Michael Wehar
CC BY-SA 3.0
2017-05-01T02:27:42.137Z
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?
Michael Wehar
CC BY-SA 3.0
2017-05-01T02:31:19.790Z
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.  :)
Michael Wehar
CC BY-SA 3.0
2017-05-01T02:35:48.130Z
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.
Michael Wehar
CC BY-SA 3.0
2017-04-30T20:26:55.720Z
2017-04-30T20:26:55.720Z
Markus Bläser
<p><strong>Background</strong></p>

<blockquote>
  <p>We know that $P^{\#P} \subseteq PSPACE$.</p>
  
  <p>In addition, we known from
  <a href="https://en.wikipedia.org/wiki/Toda%27s_theorem" rel="noreferrer">Toda's theorem</a> that $PH \subseteq P^{\#P}$.</p>
  
  <p>For more background on $\#P$, see here:
  <a href="https://en.wikipedia.org/wiki/Sharp-P" rel="noreferrer">https://en.wikipedia.org/wiki/Sharp-P</a></p>
</blockquote>

<p><strong>Question</strong></p>

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

CC BY-SA 3.0
2017-04-27T15:39:14.943Z
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}$?
Michael Lampis
CC BY-SA 3.0
2017-04-27T15:55:56.457Z
@MichaelLampis Yep, if you count the space on the query tape, then that sound right to me!  :)
Michael Wehar
CC BY-SA 3.0
2017-04-27T16:10:30.497Z
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.  :)
Michael Wehar
CC BY-SA 3.0
2017-04-28T07:10:15.717Z
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.
Markus Bläser
CC BY-SA 3.0
2017-04-28T15:15:46.397Z
@MarkusBläser Thank you very much!  I really appreciate your help.  I will have to take a look at their papers.  :)
Michael Wehar
CC BY-SA 3.0
2017-04-28T15:28:05.347Z
I took a look at the latter paper.  It seems that it contains a lot of neat related results as well.  :)
Michael Wehar
CC BY-SA 3.0
2017-04-30T10:45:02.920Z
@MarkusBläser I think you should post this as an answer.
Emil Jeřábek
<cc.complexity-theory><complexity-classes><oracles><relativization><pspace>
Does there exist an oracle $A$ such that $(P^{\#P})^{A} \neq PSPACE^{A}$?
Michael Wehar
# Does there exist an oracle $A$ such that $(P^{\#P})^{A} \neq PSPACE^{A}$?

(Asked by: username_0 on 2017-04-27)

**Background**

> We know that $P^{\#P} \subseteq PSPACE$.
>
> In addition, we known from
> [Toda's theorem](https://en.wikipedia.org/wiki/Toda%27s_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}$?

**Tags:** cc.complexity-theory, complexity-classes, oracles, relativization, pspace
> **Comments:**
> **username_1**: 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}$?  
> **username_0**: @MichaelLampis Yep, if you count the space on the query tape, then that sound right to me!  :)  
> **username_0**: 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.  :)  
> **username_2**: 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.  
> **username_0**: @MarkusBläser Thank you very much!  I really appreciate your help.  I will have to take a look at their papers.  :)  
> **username_0**: I took a look at the latter paper.  It seems that it contains a lot of neat related results as well.  :)  
> **username_3**: @MarkusBläser I think you should post this as an answer.  

---

## 1 answers

### Answer by username_2 on 2017-04-30. Score: 7 | Accepted answer

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.

> **Comments:**
> **username_0**: Just to make sure we're on the same page, is it known that $P^{PP} = P^{\#P}$?  
> **username_0**: 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?  
> **username_0**: 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.  :)  
> **username_0**: 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.  

---

