<p>I hope someone with more knowledge can supply an additional answer.</p>
<p>I don't have a reference or a survey*, but in my experience people expect that <span class="math-container">$\text{PP}\subsetneq \text{PSPACE}$</span>, mostly because, by default, complexity classes that &quot;look&quot; unequal are usually assumed to be unequal unless there is a very good reason to think otherwise; and because this heuristic has proved useful more often than not.</p>
<p>There is not much evidence for either equality or inequality. A weak form of evidence is that <span class="math-container">$\text{PP}^{O}\subsetneq \text{PSPACE}^{O}$</span> relative to a random oracle <span class="math-container">$O$</span>. Once upon a time, the Random Oracle Hypothesis conjectured that such a random oracle separation would imply a separation in the real world, but this was overturned when <span class="math-container">$\text{IP}=\text{PSPACE}$</span> was proved (which, incidentally, also overturned the assumption above, that different-looking complexity classes are always different).</p>
<p>The class <span class="math-container">$\text{PP}$</span> can be generalized to the counting hierarchy, <span class="math-container">$\text{CH}=\text{PP}\cup \text{PP}^{\text{PP}}\cup \text{PP}^{\text{PP}^{\text{PP}}}\cup\cdots$</span>. If <span class="math-container">$\text{PP}=\text{PSPACE}$</span> then also <span class="math-container">$\text{CH}=\text{PSPACE}$</span>. So, a weak form of evidence that <span class="math-container">$\text{PP}\subsetneq \text{PSPACE}$</span> would be to find an oracle relative to which <span class="math-container">$\text{CH}\subsetneq \text{PSPACE}$</span>, but such an oracle has not yet been found. A good start would be to address the second level of the counting hierarchy and find an oracle relative to which <span class="math-container">$\text{PP}^{\text{PP}}\subsetneq \text{PSPACE}$</span>, but we don't have this either.</p>
<p>*We have <a href="https://people.csail.mit.edu/rrw/likelihoods.pdf" rel="nofollow noreferrer">a survey</a> with <span class="math-container">$n=1$</span> person, namely Ryan Williams [1] gives a 50% probability to <span class="math-container">$\text{TC}^0=\text{NC}^1$</span>, and provides some reasons.
Since <span class="math-container">$\text{TC}^0=\text{NC}^1$</span> implies <span class="math-container">$\text{PP}=\text{PSPACE}$</span>, logically he gives at least 50% probability to <span class="math-container">$\text{PP}=\text{PSPACE}$</span>. (thanks to domotorp for finding this resource) An implication in the other direction is not known.</p>
<p>[1] Ryan Williams. Some Estimated Likelihoods
For Computational Complexity. <a href="https://people.csail.mit.edu/rrw/likelihoods.pdf" rel="nofollow noreferrer">https://people.csail.mit.edu/rrw/likelihoods.pdf</a></p>

CC BY-SA 4.0
2022-12-02T12:25:57.953Z
2022-12-07T09:39:47.323Z
2022-12-07T09:39:47.323Z
Lieuwe Vinkhuijzen
<p>From Googling, I couldn't find any discussion about whether <span class="math-container">$PP=PSPACE$</span> is more or less likely than <span class="math-container">$PP\subsetneq PSPACE$</span>.</p>
<blockquote>
<p><strong>Is it currently believed that <span class="math-container">$PP\neq PSPACE$</span>?</strong></p>
</blockquote>
<blockquote>
<p><strong>What would be the implications if the two happen to be equal?</strong></p>
</blockquote>

CC BY-SA 4.0
2022-12-06T07:52:30.733Z
Regarding your first question, I think it is pretty hard to tell what is 'believed' about complexity classes. They are not like, say, the prime numbers, about which you can assume some pseudorandom properties and make predictions accordingly. Here is a paper by Ryan Williams where he assigns likelihoods at random to similar questions: https://people.csail.mit.edu/rrw/likelihoods.pdf
domotorp
<cc.complexity-theory><space-complexity><pspace><probabilistic-complexity>
Is $PSPACE$ believed to be different than $PP$?
M A
# Is $PSPACE$ believed to be different than $PP$?

(Asked by: username_0 on 2022-12-01)

From Googling, I couldn't find any discussion about whether $PP=PSPACE$ is more or less likely than $PP\subsetneq PSPACE$.

> **Is it currently believed that $PP\neq PSPACE$?**

> **What would be the implications if the two happen to be equal?**

**Tags:** cc.complexity-theory, space-complexity, pspace, probabilistic-complexity

> **Comments:**
> **username_1**: Regarding your first question, I think it is pretty hard to tell what is 'believed' about complexity classes. They are not like, say, the prime numbers, about which you can assume some pseudorandom properties and make predictions accordingly. Here is a paper by Ryan Williams where he assigns likelihoods at random to similar questions: https://people.csail.mit.edu/rrw/likelihoods.pdf  

---

## 1 answers

### Answer by username_2 on 2022-12-02. Score: 11 | Accepted answer

I hope someone with more knowledge can supply an additional answer.

I don't have a reference or a survey\*, but in my experience people expect that $\text{PP}\subsetneq \text{PSPACE}$, mostly because, by default, complexity classes that "look" unequal are usually assumed to be unequal unless there is a very good reason to think otherwise; and because this heuristic has proved useful more often than not.

There is not much evidence for either equality or inequality. A weak form of evidence is that $\text{PP}^{O}\subsetneq \text{PSPACE}^{O}$ relative to a random oracle $O$. Once upon a time, the Random Oracle Hypothesis conjectured that such a random oracle separation would imply a separation in the real world, but this was overturned when $\text{IP}=\text{PSPACE}$ was proved (which, incidentally, also overturned the assumption above, that different-looking complexity classes are always different).

The class $\text{PP}$ can be generalized to the counting hierarchy, $\text{CH}=\text{PP}\cup \text{PP}^{\text{PP}}\cup \text{PP}^{\text{PP}^{\text{PP}}}\cup\cdots$. If $\text{PP}=\text{PSPACE}$ then also $\text{CH}=\text{PSPACE}$. So, a weak form of evidence that $\text{PP}\subsetneq \text{PSPACE}$ would be to find an oracle relative to which $\text{CH}\subsetneq \text{PSPACE}$, but such an oracle has not yet been found. A good start would be to address the second level of the counting hierarchy and find an oracle relative to which $\text{PP}^{\text{PP}}\subsetneq \text{PSPACE}$, but we don't have this either.

\*We have [a survey](https://people.csail.mit.edu/rrw/likelihoods.pdf) with $n=1$ person, namely Ryan Williams [1] gives a 50% probability to $\text{TC}^0=\text{NC}^1$, and provides some reasons.
Since $\text{TC}^0=\text{NC}^1$ implies $\text{PP}=\text{PSPACE}$, logically he gives at least 50% probability to $\text{PP}=\text{PSPACE}$. (thanks to username_1 for finding this resource) An implication in the other direction is not known.

[1] Ryan Williams. Some Estimated Likelihoods
For Computational Complexity. <https://people.csail.mit.edu/rrw/likelihoods.pdf>


---

