# Lower bounds on #SAT?

The problem #SAT is the canonical #P-complete problem. It's a function problem rather than a decision problem. It asks, given a boolean formula $F$ in propositional logic, how many satisfying assignments $F$ has. Which are the best lower bounds on #SAT?

To my knowledge, no one has figured out how to exploit the "counting solutions" property of #SAT in any lower bound on deterministic algorithms, so unfortunately the best known lower bounds for #SAT are basically the same as that for SAT.

However, there has been a little progress. Note that the decision version of #SAT is called "Majority-SAT": given a formula, do at least $1/2$ of the possible assignments satisfy it? "Majority-SAT" is $PP$-complete, and given an algorithm for Majority-SAT, one can solve #SAT with $O(n)$ calls to the algorithm.

The closest that people have gotten to new lower bounds for #SAT (that are not known to hold for SAT) is with lower bounds for "Majority-of-Majority-SAT": given a propositional formula over two sets of variables X and Y, for at least $1/2$ of the possible assignments to $X$, is it true that at least $1/2$ of the assignments to $Y$ make the formula satisfiable? This problem is in the "second level" of the counting hierarchy (the class $PP^{PP}$). Quantum time-space lower bounds (and more) are known for this class.

The survey at http://pages.cs.wisc.edu/~dieter/Papers/sat-lb-survey-fttcs.pdf gives an overview of results in this direction.

• Thanks for your useful answer. Thanks also for the pointer to the survey. – Giorgio Camerani Sep 8 '10 at 8:40

Also, #SAT does not have fully polynomial randomized approximation scheme (FPRAS) unless $NP=RP$.

• Could you provide a reference? – M.S. Dousti Sep 9 '10 at 12:30
• Intuitively, an FRPAS will allow you to distinguish the case of zero solutions and non-zero solutions, which is the NP-complete problem SAT. – Robin Kothari Sep 9 '10 at 14:15
• @SadeqDousti The reference is David Zuckerman, On unapproximable versions of NP-complete problems, SIAM Journal on Computing 25(6):1293-1304, 1996. Links: DOI, author's homepage. In fact, he proves the stronger result that you can't even approximate the logarithm of the number of solutions unless NP=RP. – David Richerby Sep 26 '13 at 22:39
• @DavidRicherby: I didn't expect to get an answer after 3 years! Thanks a lot :D – M.S. Dousti Sep 27 '13 at 10:58