New Length Dependent Algorithm for Maximum Satisfiability Problem

No. 5: AAAI-21 Technical Tracks 5

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 35

AAAI Technical Track on Constraint Satisfaction and Optimization

In this paper, we study the computational complexity of the Maximum Satisfiability problem in terms of the length L of a given formula. We present an algorithm with running time O(1.0927^L), hence, improving the previously known best upper bound O(1.1058^L) developed more than 20 years ago by Bansal and Raman. Theoretically speaking, our algorithm increases the length of solvable formulas by 13.3% (compare this to the recent breakthrough result for Maximum Satisfiability problem with respect to the number of clauses by Xu et al. in 2019 giving a 7.5% improvement). Besides, we propose a significantly simpler algorithm with running time O(1.1049^L). The algorithm outperforms Bansal's and Raman's algorithm in simplicity and running time.

10.1609/aaai.v35i5.16479