<p>In this post (<a href="https://cstheory.stackexchange.com/questions/1046/lower-bounds-on-sat/1049#1049">Lower bounds on #SAT?</a>) it says: &quot;given an algorithm for Majority-SAT, one can solve <a href="https://en.wikipedia.org/wiki/Sharp-SAT" rel="nofollow noreferrer">#SAT</a> with <span class="math-container">$O(n)$</span> calls to the algorithm.&quot;
What is the approach to this?</p>

CC BY-SA 4.0
2021-01-20T16:39:09.413Z
Binary search .
Emil Jeřábek
CC BY-SA 4.0
2021-01-22T06:08:12.187Z
@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
CC BY-SA 4.0
2021-01-22T07:21:17.337Z
@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
CC BY-SA 4.0
2021-01-25T07:10:42.137Z
Are you sure you didn't read that here? :) https://cstheory.stackexchange.com/questions/1046/lower-bounds-on-sat/1049#1049
Ryan Williams
<np>
Reducing #SAT to MAJ-SAT
Botanicus
# Reducing #SAT to MAJ-SAT

(Asked by: username_0 on 2021-01-20)

In this post ([Lower bounds on #SAT?](https://cstheory.stackexchange.com/questions/1046/lower-bounds-on-sat/1049#1049)) it says: "given an algorithm for Majority-SAT, one can solve [#SAT](https://en.wikipedia.org/wiki/Sharp-SAT) with $O(n)$ calls to the algorithm."
What is the approach to this?

**Tags:** np
> **Comments:**
> **username_1**: Binary search .  
> **username_2**: @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?  
> **username_1**: @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.  
> **username_3**: Are you sure you didn't read that here? :) https://cstheory.stackexchange.com/questions/1046/lower-bounds-on-sat/1049#1049  

---

## 0 answers

