3
$\begingroup$

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?

Thanks!

$\endgroup$
  • 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