New Length Dependent Algorithm for Maximum Satisfiability Problem

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. 0927L ), hence, improving the previously known best upper bound O(1. 1058L ) 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 MAXI- MUM 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. 1049L ). The algorithm outperforms Bansal’s and Raman’s algorithm in simplicity and running time.

Authors

• Vasily Alferov Independent Researcher
• Ivan Bliznets University of Groningen

Keywords

No keywords are indexed for this paper.