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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|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
@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 Aug 27 '11 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. – 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

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.

share|cite|improve this answer
Isn't this covered by Tsuyoshi and Noam's comments above? – Huck Bennett Aug 19 '14 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. – Peter Shor Aug 20 '14 at 1:13
@PeterShor I am fairly certain Daniel means this 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 Aug 20 '14 at 2:30

Your Answer


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

Not the answer you're looking for? Browse other questions tagged or ask your own question.