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.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 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.1049 L ). The algorithm outperforms Bansal's and Raman's algorithm in simplicity and running time.