New Length Dependent Algorithm for Maximum Satisfiability Problem


  • Vasily Alferov JetBrains Research
  • Ivan Bliznets HSE University St. Petersburg Department of Steklov Mathematical Institute of Russian Academy of Sciences




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.




How to Cite

Alferov, V., & Bliznets, I. (2021). New Length Dependent Algorithm for Maximum Satisfiability Problem. Proceedings of the AAAI Conference on Artificial Intelligence, 35(5), 3634-3641. Retrieved from



AAAI Technical Track on Constraint Satisfaction and Optimization