# What is the complexity of counting the number of solutions of a P-Space Complete problem? How about higher complexity classes?

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?

• You are asking a lot in one question! Aug 27, 2011 at 0:50
• #PSPACE is the same as the class of functions which can be computed in polynomial space (FPSPACE). Aug 27, 2011 at 0:58
• @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? Aug 27, 2011 at 20:59
• @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. Aug 28, 2011 at 19:10
• 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
Nov 26, 2012 at 2:14

## 1 Answer

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.

• Isn't this covered by Tsuyoshi and Noam's comments above? Aug 19, 2014 at 23:20
• 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. Aug 20, 2014 at 1:13
• @PeterShor I am fairly certain Daniel means this 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. Aug 20, 2014 at 2:30
• 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. Mar 25, 2017 at 20:26