An Improved Upper Bound for SAT

Huairui Chu; Mingyu Xiao; Zhe Zhang

AAAI 2021technical12 citations

An Improved Upper Bound for SAT

Abstract

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.

BibTeX

@inproceedings{aaai2021_animprovedupperb,
  title = {An Improved Upper Bound for SAT},
  author = {Huairui Chu and Mingyu Xiao and Zhe Zhang},
  booktitle = {AAAI 2021},
  year = {2021}
}