3
$\begingroup$

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.

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ You may get a better response by posing your question on the new CSTheory site: [ cstheory.stackexchange.com ]. $\endgroup$
    – Niel de Beaudrap
    Commented Sep 23, 2010 at 5:54
  • 1
    $\begingroup$ There aren't that many complexity classes that aren't in $\text{PH}$, but are in $\text{PSPACE}$, so there aren't that many candidates to relate to $\# \text{P}$. Polynomial time quantum computation is contained in $\text{P}^{\#\text{P}}$. I don't believe anybody knows the relationship of the existential theory of the reals to $\# \text{P}$. $\endgroup$
    – Peter Shor
    Commented Sep 23, 2010 at 21:04
  • 1
    $\begingroup$ And following up my comment, why isn't the existential theory of the reals in the complexity zoo? $\endgroup$
    – Peter Shor
    Commented Sep 23, 2010 at 21:08
  • $\begingroup$ I like the comment on $PH$ and $PSPACE$; that's a good way of looking at it. As for quantum complexity classes, I hadn't thought of those at all, but it seems very natural. After googling, I saw that en.wikipedia.org/wiki/BQP also mentions that PostBQP=PP, which is a cool relation, but since I don't know much about quantum complexity classes I'm not sure how surprising/intuitive this is. $\endgroup$
    – Huck Bennett
    Commented Sep 24, 2010 at 0:04
  • $\begingroup$ I should add that by "very natural" I mean that my layman's view of all things quantum is that they generally have probabilistic structure which of course $PP$ does. $\endgroup$
    – Huck Bennett
    Commented Sep 24, 2010 at 0:07

1 Answer 1

Reset to default
11
$\begingroup$

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

Lance Fortnow: Time-Space Tradeoffs for Satisfiability. J. Comput. Syst. Sci. 60(2): 337-353 (2000)

Improve this answer
$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .