In the realm of computational complexity, the Propositional Satisfiability problem (SAT) remains a fundamental challenge. As the first problem proven to be NP-complete, it underpins critical tasks in hardware verification, automated reasoning, and AI planning. In their 1988 research, Ramin Zabih and David McAllester proposed a novel approach to navigating the vast search trees inherent to SAT by asking a pivotal question: Which choice today will leave me with the least amount of work tomorrow?
The Challenge of Search Space Explosion
SAT solvers typically attempt to find a truth assignment for a set of variables that satisfies a logical formula in Conjunctive Normal Form (CNF). Because the number of potential assignments grows exponentially with the number of variables, solvers rely on search trees.
The order in which variables are assigned is critical; an optimal order can prune massive branches of the tree, while a poor choice leads to an "exponential explosion." Historically, solvers used static or simple local heuristics. Zabih and McAllester sought a more principled, dynamic approach based on the actual geometry of the remaining search space.
Greedy Rearrangement Strategies
The authors built upon the classic Davis-Putnam procedure and Boolean Constraint Propagation (BCP). BCP acts as the "common sense" of a SAT solver: if a clause is $(A \lor B)$ and $A$ is determined to be False, $B$ must be True. The paper introduces two "Rearrangement" algorithms designed to optimize this process:
- BCP-Reorder: A high-intelligence, high-cost strategy. At each step, it simulates the assignment of every possible remaining literal to calculate a tight upper bound on the remaining search tree size. It then selects the variable that minimizes this bound.
- Occur-Reorder: A computationally efficient alternative. It estimates the search space by counting "open binary clauses" (clauses with only two variables remaining). Since binary clauses are the primary drivers of BCP, they serve as an effective proxy for remaining work and can be calculated in constant time.
Empirical Performance
The strategies were evaluated using two primary benchmarks: the classic $n$-queens puzzle and random graph coloring problems.
The 8-Queens Benchmark
In the 8-queens test, the trade-off between "thinking" and "doing" became clear. While BCP-Reorder produced the smallest search tree, its computational overhead was prohibitive.
As shown in the table above, BCP-Reorder reduced the search size to just 316 nodes but required 1420 seconds. In contrast, Occur-Reorder achieved a significant reduction in search size (642 nodes) compared to the standard "MIN" heuristic (704 nodes) while actually running faster (8.5 seconds vs 9.7 seconds).
Random Graph Coloring
The researchers also tested 4-coloring on randomly generated graphs (50 nodes, 0.15 edge probability), which are notoriously difficult for SAT solvers.
In these more complex instances, Occur-Reorder emerged as the clear winner, roughly halving both the search tree size and the number of truth assignments required compared to existing algorithms.
Conclusion: The "Cost of Thinking"
The paper provides a masterclass in the trade-offs of algorithmic overhead. While high-level look-ahead strategies like BCP-Reorder offer the most efficient search paths theoretically, the time spent calculating those paths can outweigh the benefits. Occur-Reorder represents a practical "sweet spot," using binary clauses as a proxy for search space complexity to provide the benefits of dynamic reordering without a massive computational tax.
Future work remains to determine if these greedy bounds hold up across a broader range of logical formulas where binary clauses may be less prevalent, and whether incremental updates could eventually make high-level look-ahead strategies like BCP-Reorder viable for larger-scale problems.
Summary updated