# Solve multiple instances of SAT with a 2-approximating #SAT query

Assume we have some oracle $A$ such that when given as input a Boolean formula $\phi$, it outputs a 2-approximation to the number of satisfying assignments of $\phi$. If we are given multiple SAT instances $\phi_1,\ldots, \phi_m$ (where $m$ is a small constant such as 10, 5, or even 2), using only one query to $A$, how could I show in polynomial time which formulas are satisfiable?

Note that $\phi$ is unsatisfiable if and only if $A$ outputs 0 on input $\phi$.

• Is this homework? Jan 24 '14 at 12:12
• @KristofferArnsfeltHansen Nope, just asking out of curiosity! Jan 25 '14 at 16:49
• You should link your question on mathoverflow to this one and vice versa. Jan 25 '14 at 20:11
• @ColinMcQuillan Deleted the duplicate on mathoverflow, since you gave the answer here. Jan 25 '14 at 20:19

Here's a sketch argument for constant $m$. I'll use $Z(\cdot)$ to denote the operator that takes a formula to its number of satisfying assignments. Let $T$ be a parameter to be determined later. You can easily construct formulae $\phi'_i$ with $Z(\phi'_i)=1+2^{2^iT}Z(\phi_i)$ for each $1\leq i\leq m$. Let $\phi$ be the conjunction $\phi'_1\wedge\cdots\wedge \phi'_m$ (renaming the variable sets to be disjoint if necessary). Then $Z(\phi)=\prod_{i=1}^m(1+2^{2^iT}Z(\phi_i))$, so $\frac 1 T \log_2 Z(\phi)$ is roughly the sum of $2^i$ over all $i$ such that $\phi_i$ is satisfiable. I believe the error term is $O(n/T)$ for fixed $m$ where $n$ is the total number of variables, so taking $T$ to be a sufficiently large $T$ polynomial in $n$, you can recover which $\phi_i$ are satisfiable from a $2$-approximation to $Z(\phi)$.