5
$\begingroup$

I once read in a paper: "given an algorithm for Majority-SAT, one can solve #SAT with $O(n)$ calls to the algorithm." What is the approach to this?

$\endgroup$
4
  • 10
    $\begingroup$ Binary search . $\endgroup$ Jan 20 '21 at 16:39
  • $\begingroup$ @EmilJeřábek I did not understand. Using Majority-SAT, we can only know if more than half the assignments satisfy the formula or not. What do we do after that? What would be the reduced instance? $\endgroup$ Jan 22 '21 at 6:08
  • 3
    $\begingroup$ @Inuyashayagami Given a formula $A$ in $n$ variables and $s\le2^n$ in binary, you can easily construct a formula $B$ in, say, $n+1$ variables such that $A$ has $\ge s$ satisfying assignment iff the majority of assignments satisfy $B$. This is a simple exercise. $\endgroup$ Jan 22 '21 at 7:21
  • 2
    $\begingroup$ Are you sure you didn't read that here? :) cstheory.stackexchange.com/questions/1046/lower-bounds-on-sat/… $\endgroup$ Jan 25 '21 at 7:10
6
$\begingroup$

Emil Jeřábek's construction [Gill 1977, Simon 1975] works indeed. Assume the formula $A$ has the propositional variables $x = \langle x_1,..,x_n \rangle$ and $y$ is some fresh variable. We can then construct $B$ as a formula $(y \rightarrow A) \wedge (\neg y \rightarrow C)$ whereby the formula $C$ needs to be further specified.

For the formula $C$ we assume the threshold given binary as $s = \langle s_1,..,s_n \rangle$. We can encode the arithmetic comparison $s \leq x$ in binary form, which is the lexicographic order union equality: $\langle s_j,..,s_n \rangle \leq \langle x_j,..,x_n \rangle := (\neg s_j \wedge x_j) \vee ((s_j \leftrightarrow x_j) \wedge \langle s_{j+1},..,s_n \rangle \leq \langle x_{j+1},..,x_n \rangle)$ for $j<n$ and $(s_n \leq x_n) := (s_n \rightarrow x_n)$ otherwise.

So the formula $C$ will be just $s \leq x$. Now we have for the count of $B$:

$$|B| = |A| + |C| = |A| + 2^n-s$$

And therefore for the majority of $B$:

$$|B| \geq 2^n \Leftrightarrow |A| \geq s$$

Since $\langle 0,..,0 \rangle \leq \langle x_j,..,x_n \rangle$ is trivially true, we can even construct $C$ gradually via binary search, and thus determine $|A| = s$ by calling $n$-times the majority oracle.

$\endgroup$
7
  • $\begingroup$ In the sixth line, shouldn't it be $(\neg s_{j} \vee x_{j} )$ instead of $(\neg s_{j} \wedge x_{j})$? $\endgroup$ Jan 23 '21 at 14:09
  • $\begingroup$ (¬𝑠𝑗∧𝑥𝑗) selects 0 and 1 for the binary digits at index j of the bitvectors s and x. We can then stop checking for less than or equal s ≤ x, we only need to look for more binary digits in the case 0 and 0 or 1 and 1, but for the case 0 and 1 the matter is already decided. $\endgroup$
    – user44661
    Jan 23 '21 at 15:02
  • $\begingroup$ Thanks for explaining. I get it now. :) $\endgroup$ Jan 23 '21 at 15:38
  • 1
    $\begingroup$ Note this construction really goes all the way back to John Gill, "Computational Complexity of Probabilistic Turing Machines", SIAM J. COMPUT. Vol. 6, No. 4, December 1977. See Lemma 5.9 on p.688. $\endgroup$ Jan 27 '21 at 23:14
  • 1
    $\begingroup$ Gill took it from: Simon [25] has shown that PP is the class of languages accepted by polynomial bounded threshold machines and that #SAT and a large number of similar combinatorial problems are polynomial m-complete for threshold machines and hence for PP. $\endgroup$
    – user44661
    Jan 28 '21 at 0:16

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.