It is well known that the problem of counting the satisfying assignments of SAT, namely the problem #SAT, is #P-complete.

It is also suspected (somewhat less widely) that even deciding SAT should take time $2^{n−o(n)}$ according to the strong exponential time hypothesis.

I was wondering if there are any hardness results for APPROXIMATE-#SAT, namely counting the number of satisfying assignments up to additive errors? In particular, are there any explicit lower bounds? What if we only want to approximate up to an error of $\sqrt{2^n}$?


  • 1
    $\begingroup$ This was also cross-posted as a guest here: cs.stackexchange.com/questions/90105/… $\endgroup$
    – MGN
    Apr 2 '18 at 3:22
  • 2
    $\begingroup$ Is this homework? Take an n-variable instance I of SAT. This instance I has either 0 or >=1 satisfying truth assignments. Now generate a new instance I' by adding 2n new dummy variables to instance I that do not occur in any clause. Then 0 satisfying truth assignments for I yield 0 satisfying truth assignments for I', and >=1 satisfying assignments for I yield at least 2^(2n) satisfying assignments for I'. $\endgroup$
    – Gamow
    Apr 2 '18 at 13:00
  • $\begingroup$ This much is definitely true. I'm curious if there are any stronger lower bounds. The power of an approximate SAT counter is at least this strong, and so in principle, there may be better lower bounds. $\endgroup$
    – MGN
    Apr 2 '18 at 16:06
  • $\begingroup$ Roth, D. (1996). On the hardness of approximate reasoning. Artificial Intelligence, 82(1-2), 273-302. : not for additive error but there are many results on approximating #SAT here. $\endgroup$
    – holf
    Apr 3 '18 at 6:36

Your Answer

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

Browse other questions tagged or ask your own question.