17
$\begingroup$

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?

$\endgroup$
30
$\begingroup$

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/

$\endgroup$
1
  • $\begingroup$ Thanks for your useful answer. Thanks also for the pointer to the survey. $\endgroup$ Sep 8 '10 at 8:40
6
$\begingroup$

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

$\endgroup$
4
  • 1
    $\begingroup$ Could you provide a reference? $\endgroup$ Sep 9 '10 at 12:30
  • 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 '10 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 '13 at 22:39
  • $\begingroup$ @DavidRicherby: I didn't expect to get an answer after 3 years! Thanks a lot :D $\endgroup$ Sep 27 '13 at 10:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.