7
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ 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: people.csail.mit.edu/rrw/likelihoods.pdf $\endgroup$
    – domotorp
    Commented Dec 6, 2022 at 7:52

1 Answer 1

11
$\begingroup$

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 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 domotorp 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

$\endgroup$

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.