<p>The number of satisfying assignments to a boolean formula equals the number of valid quantifications of the formula.  The inductive proof is quite elegant. So #P = #PSpace.</p>

CC BY-SA 3.0
2014-08-19T23:20:09.037Z
Isn't this covered by Tsuyoshi and Noam's comments above?
Huck Bennett
CC BY-SA 3.0
2014-08-20T01:13:19.777Z
Is this what you really mean? If #P = #PSPACE, doesn't this imply that PSPACE $\subseteq$ P$^{\#\mathrm{P}}$ ? I don't believe this is known.
Peter Shor 
CC BY-SA 3.0
2014-08-20T02:30:47.427Z
@PeterShor I am fairly certain Daniel means this http://mathoverflow.net/a/12608/35733. But my (unverified) guess is that a #PSPACE-complete problem is to count the number of satisfying assignments of a fixed QBF, not count the number of satisfiable quantifications of a given CNF.
Sasho Nikolov
CC BY-SA 3.0
2017-03-25T20:26:09.877Z
No, I meant that the number of valid quantifications of a given cnf equals the number of satisfying assignments of the cnf, given a fixed ordering of the variables.  Its very interesting in that changing the order of variables changes the valid qbfs, but not the total number of valid qbfs.
daniel pehoushek
CC BY-SA 3.0
2014-08-19T21:43:14.790Z
2014-08-19T21:43:14.790Z
daniel pehoushek
<p>I guess it would be called #P-Space but I have found only one article vaguely mentioning it. How about the counting version of EXP-TIME-Complete, NEXP-Complete as well as EXP-SPACE-Complete problems? Is there any previous work that can one cite in regards to this or any type of inclusion or exclusion like Toda's Theorem? <br></p>

CC BY-SA 3.0
2011-08-27T00:50:15.833Z
You are asking a lot in one question!
Tsuyoshi Ito
CC BY-SA 3.0
2011-08-27T00:58:46.913Z
#PSPACE is the same as the class of functions which can be computed in polynomial space (FPSPACE).
Tsuyoshi Ito
CC BY-SA 3.0
2011-08-27T02:47:29.497Z
I think results for polytime transfer upwards using padding, don't they?
Kaveh
CC BY-SA 3.0
2011-08-27T02:47:54.800Z
Can you please explain?
Tayfun Pay
CC BY-SA 3.0
2011-08-27T20:59:12.820Z
@Tsuyoshi This is true. However, most of the questions asked if not all, can be rephrased as a single general question: Are there counting classes for classes higher than $NP$ (as one can note in the definition of #$P$) and do known results apply?
chazisop
CC BY-SA 3.0
2011-08-28T19:10:53.920Z
@Tayfun Pay: I'm not entirely sure what you mean for deterministic classes like PSPACE, EXP, EXPSPACE. The notion of "number of solutions" is usually closely tied to nondeterminism--since then you can ask about the number of accepting paths--or existential quantifiers/projections. In the case of PSPACE of course you can use the alternating quantifiers definition--but then you have to specify which quantifiers you want to count over--or the fact that NPSPACE=PSPACE.
Joshua Grochow
CC BY-SA 3.0
2012-11-26T02:14:03.173Z
As several comments mentioned, it is not totally clear what you would want to mean for #PSPACE.  The best bet would be to take the padded-up analog of #L which is well studied.  As #L is contained in DSPACE(log^2 n), this would imply that #PSPACE=PSPACE, as @TsuyoshiIto mentioned above.  (I am ignoring here the immaterial formal distinction between decision problems and functions.)
Noam
<cc.complexity-theory><complexity-classes><counting-complexity><pspace>
What is the complexity of counting the number of solutions of a P-Space Complete problem? How about higher complexity classes?
Tayfun Pay
# What is the complexity of counting the number of solutions of a P-Space Complete problem? How about higher complexity classes?

(Asked by: username_0 on 2011-08-26)

I guess it would be called #P-Space but I have found only one article vaguely mentioning it. How about the counting version of EXP-TIME-Complete, NEXP-Complete as well as EXP-SPACE-Complete problems? Is there any previous work that can one cite in regards to this or any type of inclusion or exclusion like Toda's Theorem?

**Tags:** cc.complexity-theory, complexity-classes, counting-complexity, pspace

> **Comments:**
> **username_1**: You are asking a lot in one question!  
> **username_1**: #PSPACE is the same as the class of functions which can be computed in polynomial space (FPSPACE).  
> **username_2**: I think results for polytime transfer upwards using padding, don't they?  
> **username_0**: Can you please explain?  
> **username_3**: @Tsuyoshi This is true. However, most of the questions asked if not all, can be rephrased as a single general question: Are there counting classes for classes higher than $NP$ (as one can note in the definition of #$P$) and do known results apply?  
> **username_4**: @username_0: I'm not entirely sure what you mean for deterministic classes like PSPACE, EXP, EXPSPACE. The notion of "number of solutions" is usually closely tied to nondeterminism--since then you can ask about the number of accepting paths--or existential quantifiers/projections. In the case of PSPACE of course you can use the alternating quantifiers definition--but then you have to specify which quantifiers you want to count over--or the fact that NPSPACE=PSPACE.  
> **username_5**: As several comments mentioned, it is not totally clear what you would want to mean for #PSPACE.  The best bet would be to take the padded-up analog of #L which is well studied.  As #L is contained in DSPACE(log^2 n), this would imply that #PSPACE=PSPACE, as @TsuyoshiIto mentioned above.  (I am ignoring here the immaterial formal distinction between decision problems and functions.)  

---

## 1 answers

### Answer by username_6 on 2014-08-19. Score: -5

The number of satisfying assignments to a boolean formula equals the number of valid quantifications of the formula. The inductive proof is quite elegant. So #P = #PSpace.

> **Comments:**
> **username_7**: Isn't this covered by Tsuyoshi and username_5's comments above?  
> **username_8**: Is this what you really mean? If #P = #PSPACE, doesn't this imply that PSPACE $\subseteq$ P$^{\#\mathrm{P}}$ ? I don't believe this is known.  
> **username_9**: @PeterShor I am fairly certain Daniel means this http://mathoverflow.net/a/12608/35733. But my (unverified) guess is that a #PSPACE-complete problem is to count the number of satisfying assignments of a fixed QBF, not count the number of satisfiable quantifications of a given CNF.  
> **username_6**: No, I meant that the number of valid quantifications of a given cnf equals the number of satisfying assignments of the cnf, given a fixed ordering of the variables.  Its very interesting in that changing the order of variables changes the valid qbfs, but not the total number of valid qbfs.  

---

