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?



closed as off-topic by D.W. Apr 2 '18 at 14:14

  • This question does not appear to be about computer science within the scope defined in the help center.
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    $\begingroup$ It is easy to randomly compute an additive $\epsilon 2^n$ approximation by sampling $O(1/\epsilon^2)$ assignments. This can be derandomized efficiently in the case of $k$-CNFs for fixed $k$ (this is known as approximate DNF counting). $\endgroup$ – Yuval Filmus Apr 2 '18 at 8:52
  • $\begingroup$ Cross-posted: cstheory.stackexchange.com/q/40498/5038. Please do not post the same question on multiple sites. Each community should have an honest shot at answering without anybody's time being wasted. $\endgroup$ – D.W. Apr 2 '18 at 14:13
  • $\begingroup$ I'm voting to close this question because it was cross-posted. $\endgroup$ – D.W. Apr 2 '18 at 14:14