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!

Improve this question
$\endgroup$
3
  • 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
    Commented Apr 2, 2018 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. ♦
    Commented Apr 2, 2018 at 14:13
  • $\begingroup$ I'm voting to close this question because it was cross-posted. $\endgroup$
    – D.W. ♦
    Commented Apr 2, 2018 at 14:14

0

Reset to default