An Improved Upper Bound for SAT

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

We show that the CNF satisfiability problem can be solved O^*(1.2226^m) time, where m is the number of clauses in the formula, improving the known upper bounds O^*(1.234^m) given by Yamamoto 15 years ago and O^*(1.239^m) given by Hirsch 22 years ago. By using an amortized technique and careful case analysis, we successfully avoid the bottlenecks in previous algorithms and get the improvement.

10.1609/aaai.v35i5.16487