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

<p>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.</p>

<p>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}$?</p>

<p>Thanks!</p>

CC BY-SA 3.0
2018-04-02T03:22:46.823Z
This was also cross-posted as a guest here: https://cs.stackexchange.com/questions/90105/how-hard-is-approximate-sat
squiggles
CC BY-SA 3.0
2018-04-02T13:00:40.743Z
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'.
Gamow
CC BY-SA 3.0
2018-04-02T16:06:11.233Z
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.
squiggles
CC BY-SA 3.0
2018-04-03T06:36:49.933Z
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.
holf
<cc.complexity-theory><sat><lower-bounds><counting-complexity><approximation>
How hard is APPROXIMATE-#SAT?
squiggles
# How hard is APPROXIMATE-#SAT?

(Asked by: username_0 on 2018-04-02)

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}$?

Thanks!

**Tags:** cc.complexity-theory, sat, lower-bounds, counting-complexity, approximation
> **Comments:**
> **username_0**: This was also cross-posted as a guest here: https://cs.stackexchange.com/questions/90105/how-hard-is-approximate-sat  
> **username_1**: 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'.  
> **username_0**: 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.  
> **username_2**: 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.  

---

## 0 answers

