Lower bounds on #SAT?

Question

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?

Answer 1

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/

Answer 2

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