5
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Is this homework? $\endgroup$ – Kristoffer Arnsfelt Hansen Jan 24 '14 at 12:12
  • $\begingroup$ @KristofferArnsfeltHansen Nope, just asking out of curiosity! $\endgroup$ – matthon Jan 25 '14 at 16:49
  • 1
    $\begingroup$ You should link your question on mathoverflow to this one and vice versa. $\endgroup$ – Colin McQuillan Jan 25 '14 at 20:11
  • $\begingroup$ @ColinMcQuillan Deleted the duplicate on mathoverflow, since you gave the answer here. $\endgroup$ – matthon Jan 25 '14 at 20:19
5
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.