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
5  
You are asking a lot in one question! –  Tsuyoshi Ito Aug 27 '11 at 0:50
3  
#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
4  
@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
4  
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

1 Answer 1

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|improve this answer
2  
Isn't this covered by Tsuyoshi and Noam's comments above? –  Huck Bennett Aug 19 at 23:20
1  
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
3  
@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. –  Sasho Nikolov Aug 20 at 2:30

Your Answer

 
discard

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.