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

CC BY-SA 3.0
2014-01-25T20:11:13.443Z
2014-01-26T07:43:52.440Z
2014-01-26T07:43:52.440Z
Colin McQuillan
<p>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?</p>

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

CC BY-SA 3.0
2014-01-24T12:12:18.733Z
Is this homework?
Kristoffer Arnsfelt Hansen
CC BY-SA 3.0
2014-01-25T16:49:58.373Z
@KristofferArnsfeltHansen Nope, just asking out of curiosity!
matthon
CC BY-SA 3.0
2014-01-25T20:11:37.650Z
You should link your question on mathoverflow to this one and vice versa.
Colin McQuillan
CC BY-SA 3.0
2014-01-25T20:19:02.130Z
@ColinMcQuillan Deleted the duplicate on mathoverflow, since you gave the answer here.
matthon
<cc.complexity-theory><sat><counting-complexity>
Solve multiple instances of SAT with a 2-approximating #SAT query
matthon
# Solve multiple instances of SAT with a 2-approximating #SAT query

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

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$.

**Tags:** cc.complexity-theory, sat, counting-complexity
> **Comments:**
> **username_1**: Is this homework?  
> **username_0**: @KristofferArnsfeltHansen Nope, just asking out of curiosity!  
> **username_2**: You should link your question on mathoverflow to this one and vice versa.  
> **username_0**: @ColinMcQuillan Deleted the duplicate on mathoverflow, since you gave the answer here.  

---

## 1 answers

### Answer by username_2 on 2014-01-25. Score: 6 | Accepted answer

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)$.


---

