# 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

• 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