<p>Here is a reference to <a href="http://arxiv.org/abs/0908.2122" rel="nofollow">Bordewich, Freedman, Lovász, and Welsh</a> that develops this topic to some extent.</p>

CC BY-SA 3.0
2014-05-02T12:12:49.027Z
2014-05-02T12:12:49.027Z
Martin Schwarz
<p>We're interested in additive approximations to #3SAT. i.e. given a 3CNF $\phi$ on $n$ variables count the number of satisfying assignments (call this $a$) up to additive error $k$.</p>

<p>Here are some basic results for this:</p>

<p><b>Case 1:</b> $k=2^{n-1}-\mathrm{poly}(n)$</p>

<p>Here there is a deterministic poly-time algorithm: Let $m=2^n-2k = \mathrm{poly}(n)$. Now evaluate $\phi$ on $m$ arbitrary inputs (e.g. the lexicographically first $m$ inputs). Suppose $\ell$ of these inputs satisfy $\phi$. Then we know $a \geq \ell$ as there are at least $\ell$ satisfying assignments and $a \leq 2^n - (m-\ell)$ as there are at least $m-\ell$ unsatisfying assignments. The length of this interval is $2^n - (m-\ell) - \ell = 2k$. So if we output the midpoint $2^{n-1} -m/2 + \ell$ this is within $k$ of the correct answer, as required.</p>

<p><b>Case 2:</b> $k=2^n/\mathrm{poly}(n)$</p>

<p>Here we have a randomized poly-time algorithm: Evaluate $\phi$ at $m$ random points $X_1, \cdots, X_m \in \{0,1\}^n$. Let $\alpha = \frac{1}{m} \sum_{i=1}^m \phi(X_i)$ and $\varepsilon = k/2^n$. We output $2^n \cdot \alpha$. For this to have error at most $k$ we need $$k \geq |2^n \alpha - a| = 2^n |\alpha - a/2^n|,$$ which is equivalent to $|\alpha - a/2^n| \leq \varepsilon.$ By a <a href="http://terrytao.wordpress.com/2010/01/03/254a-notes-1-concentration-of-measure/">Chernoff bound</a>, $$\mathbb{P}[|\alpha - a/2^n| &gt; \varepsilon] \leq 2^{-\Omega(m \varepsilon^2)},$$ as $\mathbb{E}[\phi(X_i)]=\mathbb{E}[\alpha]=a/2^n$.
This implies that, if we choose $m=O(1/\varepsilon^2) = \mathrm{poly}(n)$ (and ensure $m$ is a power of $2$), then with probability at least $0.99$, the error is at most $k$.</p>

<p><b>Case 3:</b> $k=2^{cn + o(n)}$ for $c &lt; 1$</p>

<p>In this case the problem is #P-hard: We will do a reduction from #3SAT. Take a 3CNF $\psi$ on $m$ variables. Pick $n \geq m$ such that $k &lt; 2^{n-m-1}$ -- this requires $n = O(m/(1-c))$. Let $\phi=\psi$ except $\phi$ is now on $n$ variables, rather than $m$. If $\psi$ has $b$ satisfying assignments, then $\phi$ has $b \cdot 2^{n-m}$ satisfying assignments, as the $n-m$ "free" variables can take any value in a satisfying assignment. Now suppose we have $\hat{a}$ such that $|\hat{a}-a| \leq k$ -- that is $\hat{a}$ is an approximation to the number of satisfying assignments of $\phi$ with additive error $k$. Then $$|b-\hat{a}/2^{n-m}| = \left| \frac{a - \hat{a}}{2^{n-m}}\right| \leq \frac{k}{2^{n-m}} &lt; 1/2.$$
Since $b$ is an integer, this means we can determine the exact value of $b$ from $\hat{a}$. Algorithmically determining the exact value of $b$ entails solving the #P-complete problem #3SAT. This means that it is #P-hard to compute $\hat{a}$.</p>

CC BY-SA 3.0
2014-05-01T23:25:08.227Z
2014-05-01T23:25:08.227Z
Thomas Steinke
<p>Consider the classical #P-complete problem #3SAT, i.e., to count the number of valuations to make a 3CNF with $n$ variables satisfiable. I am interested in the <strong>additive</strong> approximability. Clearly, there is a trivial algorithm to achieve $2^{n-1}$-error, but if $k&lt;2^{n-1}$, is it possible to have an efficient approximation algorithm, or this problem is also #P-hard?</p>

CC BY-SA 3.0
2014-05-01T22:16:49.407Z
If $k=2^{n-1}-\mathrm{poly}(n)$, then there is a poly-time algorithm with additive error $k$. If $k=2^{n}/\mathrm{poly}(n)$, then there would be a randomized poly-time algorithm with additive error $k$. When $k$ is significantly smaller (but not polynomially small), I would expect it to be NP-hard, but not #P-hard, as #P hardness usually depends on it being an exact computation.
Thomas Steinke
CC BY-SA 3.0
2014-05-01T22:32:04.527Z
Could you provide reference for the first two claims? Sorry I am a beginner ...
user0928
<approximation-algorithms><sat><counting-complexity><approximation-hardness>
Approximating #P-hard problems
user0928
# Approximating #P-hard problems

(Asked by: username_0 on 2014-05-01)

Consider the classical #P-complete problem #3SAT, i.e., to count the number of valuations to make a 3CNF with $n$ variables satisfiable. I am interested in the **additive** approximability. Clearly, there is a trivial algorithm to achieve $2^{n-1}$-error, but if $k<2^{n-1}$, is it possible to have an efficient approximation algorithm, or this problem is also #P-hard?

**Tags:** approximation-algorithms, sat, counting-complexity, approximation-hardness

> **Comments:**
> **username_1**: If $k=2^{n-1}-\mathrm{poly}(n)$, then there is a poly-time algorithm with additive error $k$. If $k=2^{n}/\mathrm{poly}(n)$, then there would be a randomized poly-time algorithm with additive error $k$. When $k$ is significantly smaller (but not polynomially small), I would expect it to be NP-hard, but not #P-hard, as #P hardness usually depends on it being an exact computation.  
> **username_0**: Could you provide reference for the first two claims? Sorry I am a beginner ...  

---

## 2 answers

### Answer by username_1 on 2014-05-01. Score: 12 | Accepted answer

We're interested in additive approximations to #3SAT. i.e. given a 3CNF $\phi$ on $n$ variables count the number of satisfying assignments (call this $a$) up to additive error $k$.

Here are some basic results for this:

**Case 1:** $k=2^{n-1}-\mathrm{poly}(n)$

Here there is a deterministic poly-time algorithm: Let $m=2^n-2k = \mathrm{poly}(n)$. Now evaluate $\phi$ on $m$ arbitrary inputs (e.g. the lexicographically first $m$ inputs). Suppose $\ell$ of these inputs satisfy $\phi$. Then we know $a \geq \ell$ as there are at least $\ell$ satisfying assignments and $a \leq 2^n - (m-\ell)$ as there are at least $m-\ell$ unsatisfying assignments. The length of this interval is $2^n - (m-\ell) - \ell = 2k$. So if we output the midpoint $2^{n-1} -m/2 + \ell$ this is within $k$ of the correct answer, as required.

**Case 2:** $k=2^n/\mathrm{poly}(n)$

Here we have a randomized poly-time algorithm: Evaluate $\phi$ at $m$ random points $X\_1, \cdots, X\_m \in \{0,1\}^n$. Let $\alpha = \frac{1}{m} \sum\_{i=1}^m \phi(X\_i)$ and $\varepsilon = k/2^n$. We output $2^n \cdot \alpha$. For this to have error at most $k$ we need $$k \geq |2^n \alpha - a| = 2^n |\alpha - a/2^n|,$$ which is equivalent to $|\alpha - a/2^n| \leq \varepsilon.$ By a [Chernoff bound](http://terrytao.wordpress.com/2010/01/03/254a-notes-1-concentration-of-measure/), $$\mathbb{P}[|\alpha - a/2^n| > \varepsilon] \leq 2^{-\Omega(m \varepsilon^2)},$$ as $\mathbb{E}[\phi(X\_i)]=\mathbb{E}[\alpha]=a/2^n$.
This implies that, if we choose $m=O(1/\varepsilon^2) = \mathrm{poly}(n)$ (and ensure $m$ is a power of $2$), then with probability at least $0.99$, the error is at most $k$.

**Case 3:** $k=2^{cn + o(n)}$ for $c < 1$

In this case the problem is #P-hard: We will do a reduction from #3SAT. Take a 3CNF $\psi$ on $m$ variables. Pick $n \geq m$ such that $k < 2^{n-m-1}$ -- this requires $n = O(m/(1-c))$. Let $\phi=\psi$ except $\phi$ is now on $n$ variables, rather than $m$. If $\psi$ has $b$ satisfying assignments, then $\phi$ has $b \cdot 2^{n-m}$ satisfying assignments, as the $n-m$ "free" variables can take any value in a satisfying assignment. Now suppose we have $\hat{a}$ such that $|\hat{a}-a| \leq k$ -- that is $\hat{a}$ is an approximation to the number of satisfying assignments of $\phi$ with additive error $k$. Then $$|b-\hat{a}/2^{n-m}| = \left| \frac{a - \hat{a}}{2^{n-m}}\right| \leq \frac{k}{2^{n-m}} < 1/2.$$
Since $b$ is an integer, this means we can determine the exact value of $b$ from $\hat{a}$. Algorithmically determining the exact value of $b$ entails solving the #P-complete problem #3SAT. This means that it is #P-hard to compute $\hat{a}$.


---

### Answer by username_2 on 2014-05-02. Score: 4

Here is a reference to [Bordewich, Freedman, Lovász, and Welsh](http://arxiv.org/abs/0908.2122) that develops this topic to some extent.


---

