Measuring the Hardness of SAT Instances

Carlos Ansótegui, Maria Luisa Bonet, Jordi Levy, Felip ManyàAAAI 2008

Introduction

The Boolean Satisfiability Problem (SAT) is a cornerstone of computational complexity, famously known as the first NP-complete problem. Despite its theoretical difficulty, modern SAT solvers routinely handle industrial instances with millions of variables in seconds. This discrepancy raises a fundamental question: what structural properties actually determine the "hardness" of a SAT instance? Traditional measures like treewidth or strong backdoors often fail to capture the practical difficulty experienced by solvers. This paper proposes tree-like space complexity—derived from the Horton-Strahler number—as a more accurate metric for quantifying instance hardness in DPLL-based solvers.

Defining Space via Strahler Numbers

The authors define the "space" of a formula based on its tree-like resolution proofs. They utilize the Horton-Strahler number, a concept originally from hydrology used to describe river branching. In the context of SAT, it represents the minimum number of memory slots (or pointers) required to traverse a resolution proof tree.

A tree-like resolution proof structure illustrating the hierarchical derivation of clauses.

The space ($s$) of a formula is the minimum Strahler number among all its possible tree-like refutations. Theoretically, the authors demonstrate that if a formula has space $s$, its satisfiability can be determined in $O(n^{s+1})$ time, providing a direct link between this structural measure and computational effort.

Experimental Methodology

To validate space as a hardness measure, the researchers developed strahler-satz, a modified version of the satz solver. This tool estimates the space of an instance by measuring the Strahler number of the search tree generated during execution. The study evaluated two primary datasets:

  1. Random 3-SAT Instances: Generated with 100 to 500 variables and varying clause-to-variable ratios to observe the "phase transition."
  2. Industrial Benchmarks: Real-world problems from hardware verification, planning, and logistics sourced from the SAT Solver Competition 2005.

Key Findings: The Phase Transition and Industrial Simplicity

The experimental results highlight two significant insights. First, in random 3-SAT instances, the space complexity peaks precisely at the known "phase transition" point (a clause-to-variable ratio of approximately 4.25), where problems are empirically hardest to solve.

The percentage of Strahler number relative to variables peaks at the phase transition (~4.25 ratio) for random 3-SAT instances across different variable counts.

Second, the study reveals the surprising "simplicity" of industrial instances. Despite their massive size, many industrial problems exhibit remarkably low space requirements. For instance, a hardware verification problem with over 2,000 variables was found to have a space of only 7. This low space complexity explains why these instances are tractable: their underlying proof trees are highly "unbalanced," allowing solvers to navigate them with minimal memory and search depth.

Conclusion

Tree-like space complexity offers a robust and flexible measure of SAT hardness that aligns more closely with solver behavior than previous structural metrics. While currently limited to tree-like resolution (DPLL), extending this concept to general resolution and Conflict-Driven Clause Learning (CDCL) solvers remains a promising avenue for future research. Understanding the low-space nature of industrial problems could lead to more specialized and efficient solving techniques tailored to these specific structures.

Summary updated

BibTeX
@inproceedings{ansotegui2008measuring,
  author = {Carlos Ansótegui and Maria Luisa Bonet and Jordi Levy and Felip Manyà},
  title = {{Measuring the Hardness of SAT Instances}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2008},
}
Figure