Approximating #P-hard problems

Question

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?

Answer 1

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, $$\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 2

Here is a reference to Bordewich, Freedman, Lovász, and Welsh that develops this topic to some extent.