MAJORITY-3SAT (and Related Problems) in Polynomial Time

Shyan Akmal, Ryan Williams

Majority-SAT is the problem of determining whether an input $n$-variable formula in conjunctive normal form (CNF) has at least $2^{n-1}$ satisfying assignments. Majority-SAT and re…