New Algorithms for #2-SAT and #3-SAT
By: Junqiang Peng, Zimo Sheng, Mingyu Xiao
Potential Business Impact:
Counts ways to solve hard logic puzzles faster.
The #2-SAT and #3-SAT problems involve counting the number of satisfying assignments (also called models) for instances of 2-SAT and 3-SAT, respectively. In 2010, Zhou et al. proposed an $\mathcal{O}^*(1.1892^m)$-time algorithm for #2-SAT and an efficient approach for #3-SAT, where $m$ denotes the number of clauses. In this paper, we show that the weighted versions of #2-SAT and #3-SAT can be solved in $\mathcal{O}^*(1.1082^m)$ and $\mathcal{O}^*(1.4423^m)$ time, respectively. These results directly apply to the unweighted cases and achieve substantial improvements over the previous results. These advancements are enabled by the introduction of novel reduction rules, a refined analysis of branching operations, and the application of path decompositions on the primal and dual graphs of the formula.
Similar Papers
On the Regularity of Random 2-SAT and 3-SAT
Probability
Finds how many clues are needed to solve puzzles.
A Critique of Quigley's "A Polynomial Time Algorithm for 3SAT"
Computational Complexity
Proves a computer puzzle solver doesn't work.
An Intrinsic Barrier for Resolving P = NP (2-SAT as Flat, 3-SAT as High-Dimensional Void-Rich)
Computational Complexity
Makes hard computer problems harder to solve.