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?

2 Answers

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.

UPDATE: As of 2019, the first paragraph in the above is obsolete. It is known that #SAT requires a time-space product that is basically $$n^2$$. See for example "Quadratic Time-Space Lower Bounds for Computing Natural Functions with a Random Oracle" https://drops.dagstuhl.de/opus/volltexte/2018/10149/

• Thanks for your useful answer. Thanks also for the pointer to the survey. 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? 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. 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. Sep 26 '13 at 22:39
• @DavidRicherby: I didn't expect to get an answer after 3 years! Thanks a lot :D Sep 27 '13 at 10:58