# 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! –  Tsuyoshi Ito Aug 27 '11 at 0:50
#PSPACE is the same as the class of functions which can be computed in polynomial space (FPSPACE). –  Tsuyoshi Ito Aug 27 '11 at 0:58
I think results for polytime transfer upwards using padding, don't they? –  Kaveh Aug 27 '11 at 2:47
@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 Aug 28 '11 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 '12 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. –  Peter Shor Aug 20 at 1:13