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.

$\endgroup$
5
  • 1
    $\begingroup$ You may get a better response by posing your question on the new CSTheory site: [ cstheory.stackexchange.com ]. $\endgroup$ 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
    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
    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$ 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$ Sep 24, 2010 at 0:07

1 Answer 1

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)

$\endgroup$
0

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.