6

In this post (Lower bounds on #SAT?) it says: "given an algorithm for Majority-SAT, one can solve #SAT with $O(n)$ calls to the algorithm." What is the approach to this?

Botanicus
  • 71
  • 3
  • 11
    Binary search . – Emil Jeřábek Jan 20 '21 at 16:39
  • @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? – Inuyasha Yagami Jan 22 '21 at 06:08
  • 3
    @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. – Emil Jeřábek Jan 22 '21 at 07:21
  • 2
    Are you sure you didn't read that here? :) https://cstheory.stackexchange.com/questions/1046/lower-bounds-on-sat/1049#1049 – Ryan Williams Jan 25 '21 at 07:10

1 Answers1

8

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.

  • In the sixth line, shouldn't it be $(\neg s_{j} \vee x_{j} )$ instead of $(\neg s_{j} \wedge x_{j})$? – Inuyasha Yagami Jan 23 '21 at 14:09
  • (¬∧) 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. –  Jan 23 '21 at 15:02
  • Thanks for explaining. I get it now. :) – Inuyasha Yagami Jan 23 '21 at 15:38
  • 1
    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. – Ryan Williams Jan 27 '21 at 23:14
  • 2
    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. –  Jan 28 '21 at 00:16
  • Simon [25] is not behind paywall. But frankly less readable than Gill: https://ecommons.cornell.edu/bitstream/handle/1813/6975/75-224.pdf?sequence=1&isAllowed=y –  Jan 28 '21 at 00:23
  • Good point! Often Gill and Simon are given joint credit for this. In general Simon's PhD thesis is a great read. – Ryan Williams Jan 28 '21 at 15:43