18
$\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$

2 Answers 2

31
$\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, 2010 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, 2010 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, 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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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