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

arXiv: https://arxiv.org/abs/2107.02748 · HTML: https://mlsanity.com/paper/2107.02748/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 4 of its 57 references that are in the map.
- First posted on arXiv 6 Jul 2021.

## Builds on (most cited first, 4 of 4)

- [Optimal Value of Information in Graphical Models](https://mlsanity.com/paper/1401.3474/) (2014)
- [The Complexity of Bayesian Networks Specified by Propositional and Relational Languages](https://mlsanity.com/paper/1612.01120/) (2016)
- [Fine-grained reductions from approximate counting to decision](https://mlsanity.com/paper/1707.04609/) (2017)
- [Breaking the 2n barrier for 5-coloring and 6-coloring](https://mlsanity.com/paper/2007.10790/) (2020)

## Built on by (most cited first, 1 of 1)

- [Checking Leakage Witnesses versus Certifying Bounded Non-Leakage](https://mlsanity.com/paper/2609.32134/) (2026)

## Abstract (arXiv)

Majority-SAT is the problem of determining whether an input n-variable formula in conjunctive normal form (CNF) has at least 2n-1 satisfying assignments. Majority-SAT and related problems have been studied extensively in various AI communities interested in the complexity of probabilistic planning and inference. Although Majority-SAT has been known to be PP-complete for over 40 years, the complexity of a natural variant has remained open: Majority-kSAT, where the input CNF formula is restricted to have clause width at most k. We prove that for every k, Majority-kSAT is in P. In fact, for any positive integer k and rational ρ ∈ (0,1) with bounded denominator, we give an algorithm that can determine whether a given k-CNF has at least ρ · 2n satisfying assignments, in deterministic linear time (whereas the previous best-known algorithm ran in exponential time). Our algorithms have interesting positive implications for counting complexity and the complexity of inference, significantly reducing the known complexities of related problems such as E-MAJ-kSAT and MAJ-MAJ-kSAT. At the heart of our approach is an efficient method for solving threshold counting problems by extracting sunflowers found in the corresponding set system of a k-CNF. We also show that the tractability of Majority-kSAT is somewhat fragile. For the closely related GtMajority-SAT problem (where we ask whether a given formula has greater than 2n-1 satisfying assignments) which is known to be PP-complete, we show that GtMajority-kSAT is in P for k≤ 3, but becomes NP-complete for k≥ 4. These results are counterintuitive, because the ``natural'' classifications of these problems would have been PP-completeness, and because there is a stark difference in the complexity of GtMajority-kSAT and Majority-kSAT for all k≥ 4.