Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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?

share|improve this question
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
show 3 more comments

Your Answer


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

Browse other questions tagged or ask your own question.