An Improved Upper Bound for SAT

Huairui Chu, Mingyu Xiao, Zhe ZhangAAAI 2021 · DOI

Abstract

The Boolean Satisfiability (SAT) problem is a fundamental NP-complete problem in computer science. While polynomial-time solutions remain elusive, refining the upper bounds for exact algorithms is a critical area of theoretical research. This paper improves the upper bound for solving SAT relative to the number of clauses ($m$) from $O^*(1.234^m)$ to $O^*(1.2226^m)$. This result, achieved through sophisticated amortized analysis and new branching rules, represents the first major improvement in this metric in over fifteen years.

Introduction

The Boolean Satisfiability problem (SAT) serves as the cornerstone of computational complexity theory. Given the unlikelihood of finding a polynomial-time algorithm, research focuses on optimizing "exact" algorithms that guarantee a solution or a proof of unsatisfiability. Performance is typically measured against three metrics: the number of variables ($n$), the total formula length ($L$), and the number of clauses ($m$).

For over a decade, the theoretical community faced a plateau regarding the $m$-based bound. The previous state-of-the-art, $O^*(1.234^m)$, was established by Yamamoto in 2005. The primary bottleneck was the presence of "(3,3)-literals"—variables appearing three times positively and three times negatively—which resisted efficient reduction using standard branching techniques.

Methodology

As a theoretical study, this work relies on mathematical proofs rather than empirical datasets. The authors employ a branch-and-search framework, enhanced by three primary innovations:

1. Advanced Reduction Rules

The algorithm incorporates rules based on "autarkic sets"—subsets of literals that can be satisfied without negatively impacting the remaining clauses. These rules allow for more aggressive pruning of the search tree compared to standard simplification techniques.

2. Formula Classification

To handle the complexity of branching, formulas are categorized into "Good" and "Bad" states. "Bad" formulas are those that are highly restricted, lacking simple shortcuts and containing problematic literal frequencies. This classification allows the algorithm to apply targeted strategies based on the formula's structural properties.

3. Amortized Analysis

The core of the improvement lies in a "substitution method" for amortized analysis. Rather than requiring every individual branching step to meet a strict efficiency threshold, the authors prove that "bad" (slower) branching steps inevitably transform the formula into a "Good" state. In these subsequent states, branching becomes significantly more efficient, leading to a better overall worst-case bound when averaged across the search path.

Detailed case analysis of literal frequencies and branching factors used in the proof.

Key Insights: Breaking the (3,3) Bottleneck

The breakthrough involves a deep structural analysis of how literals interact. By identifying "coincident pairs"—literals that appear together in multiple clauses—the authors developed specific branching rules for previously intractable cases. Specifically, they proved that branching on a (3,3)-literal in a "Bad" formula always yields "Good" sub-formulas, effectively bypassing the historical bottleneck.

Results

The paper establishes a new theoretical state-of-the-art for SAT complexity. While the numerical shift from 1.234 to 1.2226 may appear incremental, the exponential nature of the complexity means this result significantly reduces the search space for large-scale formulas.

Comparison of SAT upper bounds relative to the number of clauses m, showing the improvement over previous records.

Conclusion

This research narrows the gap in the theoretical understanding of SAT complexity. While modern Conflict-Driven Clause Learning (CDCL) solvers often outperform these theoretical bounds on practical, real-world instances, they lack the same worst-case guarantees. Future work remains focused on further refining these bounds and potentially incorporating practical solver heuristics into formal theoretical proofs.

Summary updated

BibTeX
@inproceedings{chu2021improved,
  author = {Huairui Chu and Mingyu Xiao and Zhe Zhang},
  title = {{An Improved Upper Bound for SAT}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.1609/aaai.v35i5.16487},
}

Loading related content...

Figure