The counting class $\text{#P}$ and the related decision class $PP$ both involve counting the number of certificates to $NP$ problems.
Because $\text{#P}$ counts certificates, it seems obvious that $NP \subseteq \text{#P}$ and $co-NP \subseteq \text{#P}$. Furthermore, we can find any certificates using a brute force search, so $\text{#P} \subseteq EXP$.
The most interesting result that I found in Arora and Barak is Toda's Theorem which states that $PH \subseteq P^{\text{#SAT}}$, $\text{#SAT}$ being a $\text{#P}$-complete problem.
I'm wondering if there are any other results which relate $\text{#P}$ or $PP$ to other complexity classes, and what relationships are conjectured. For example, is it conjectured or known that $\text{#P} \subsetneq PSPACE$ ?
It occurred to me that because $\text{#P}$ is not a decision class some of these relationship may not be well-defined, but then again it seems natural enough to wonder how much time and space it takes to compute non-boolean (i.e. non-decision) functions of languages. Arora and Barak call Toda's Theorem a "big surprise", since as they put it $\text{#P}$ and $PH$ "both are natural generalizations of $NP$, but it seemed that their features … are not directly comparable to each other". Given that result I'm hopeful that $\text{#P}$ can be related to other classes.
Best Answer
It is not known that $PP \subsetneq PSPACE$, but it is natural to conjecture it. What people really believe on this subject is murky territory. The fact that $P^{PP}$ contains the polynomial hierarchy is, to me, evidence that $P^{PP} = PSPACE$.
Let $a(n)$ be an unbounded time-constructible function. One example of a class which is "between" the polynomial hierarchy and $PSPACE$ is $\Sigma_{a(n)} P$, the class of languages recognized by an alternating machine that makes $O(a(n))$ alternations on inputs of length $n$. It is not known for example if $\Sigma_{a(n)} P \subseteq P^{PP}$ for any unbounded $a(n)$. If you were going to prove that $P^{PP} = PSPACE$, you would want to start by putting some "unbounded levels of the polynomial hierarchy" in $P^{PP}$ first. However, it may be helpful to know that by doing so, you would separate $PP$ from $LOGSPACE$. For all unbounded $a(n)$, we have $LOGSPACE \subsetneq \Sigma_{a(n)} P$; this was proved in