Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
1  
You may get a better response by posing your question on the new CSTheory site: [ cstheory.stackexchange.com ]. –  Niel de Beaudrap Sep 23 '10 at 5:54
1  
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}$. –  Peter Shor Sep 23 '10 at 21:04
    
And following up my comment, why isn't the existential theory of the reals in the complexity zoo? –  Peter Shor Sep 23 '10 at 21:08
    
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. –  Huck Bennett Sep 24 '10 at 0:04
    
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. –  Huck Bennett Sep 24 '10 at 0:07

1 Answer 1

up vote 11 down vote accepted

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)

share|improve this answer
    
Nice answer, thanks! –  Huck Bennett Sep 29 '10 at 3:54

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.