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/
-
$\begingroup$ Thanks for your useful answer. Thanks also for the pointer to the survey. $\endgroup$ Sep 8, 2010 at 8:40
Also, #SAT does not have fully polynomial randomized approximation scheme (FPRAS) unless $NP=RP$.
-
1
-
2$\begingroup$ Intuitively, an FRPAS will allow you to distinguish the case of zero solutions and non-zero solutions, which is the NP-complete problem SAT. $\endgroup$ Sep 9, 2010 at 14:15
-
1$\begingroup$ @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. $\endgroup$ Sep 26, 2013 at 22:39
-
$\begingroup$ @DavidRicherby: I didn't expect to get an answer after 3 years! Thanks a lot :D $\endgroup$ Sep 27, 2013 at 10:58