Theoretical Analysis of Davis-Putnam Procedure and Propositional Satisfiability

Nobuhiro Yugami

Abstract

This paper provides a rigorous statistical analysis of the Davis-Putnam (DP) procedure, the foundational algorithm for solving Boolean Satisfiability (SAT). By focusing on the "fixed clause length" model, the author successfully predicts the "hardest" instances of SAT, demonstrating that computational complexity peaks sharply at the phase transition where a formula has a 50% chance of being satisfiable.

Introduction

Propositional Satisfiability (SAT) is a cornerstone of computational complexity theory, famously known as the first problem proven to be NP-complete. Despite its worst-case exponential time complexity, many real-world and random instances are solved efficiently in practice. Early theoretical models often suggested that SAT could be solved in polynomial time on average, but these findings frequently clashed with experimental observations.

The primary discrepancy lay in the distribution of test formulas. This research addresses the need for a theoretical framework that explains the "average-case" behavior of SAT solvers under the fixed clause length model (k-SAT). Specifically, it seeks to quantify why problem difficulty changes drastically based on the ratio of clauses ($M$) to variables ($N$).

Methodology

The study analyzes a variant of the Davis-Putnam procedure known as SDP (Simplified Davis-Putnam). The DP procedure relies on two primary mechanisms:

  1. Unit Propagation: Automatically assigning values to variables in clauses with only one literal remaining.
  2. Splitting Rule: A backtracking search mechanism that guesses variable values when no unit clauses are present.

The author developed a series of recursion formulas to model the statistical evolution of a formula during the search process. By tracking the probabilities of clauses becoming "empty" (unsatisfiable) or "unit," the model derives theoretical estimates for the probability of satisfiability ($P_{satisfiable}$), the complexity of finding a single solution ($ac_{check}$), and the complexity of finding all solutions ($ac_{all}$). Synthetic benchmarks for 3-SAT and 4-SAT with $N=50$ variables were used to validate these theoretical predictions against empirical data.

Results and Key Insights

The most significant finding is the theoretical confirmation of the "crossover point"—the specific clause-to-variable ratio where the probability of satisfiability is exactly 0.5. This point marks the peak of computational difficulty for SAT solvers.

Comparison of statistical predictions and empirical results for 3-SAT (top) and 4-SAT (bottom) across satisfiability and complexity metrics.

As illustrated in the figure above, the statistical model predicted crossover points at ratios of approximately 4.6 for 3-SAT and 10.4 for 4-SAT, aligning closely with empirical results (4.3 and 10.0, respectively). The complexity curves for satisfiability checking ($ac_{check}$) exhibit a sharp "hump" at these transitions.

The analysis reveals that the efficiency of DP-based solvers is heavily driven by unit propagation's ability to prune the search tree. Furthermore, the model for finding all solutions ($ac_{all}$) proved remarkably accurate, as this metric is less sensitive to the "luck" of initial branching choices compared to finding a single solution.

Conclusion and Future Work

The provided statistical framework offers a powerful tool for predicting the performance of SAT solvers on random instances. While the model slightly underestimates complexity in the highly constrained "unsatisfiable" region due to approximations in sub-problem overlap, its overall accuracy is high. Future research focusing on more refined approximations of these overlaps could lead to even more precise complexity predictions, further bridging the gap between SAT theory and practice.

Summary updated

BibTeX
@inproceedings{yugami1995theoretical,
  author = {Nobuhiro Yugami},
  title = {{Theoretical Analysis of Davis-Putnam Procedure and Propositional Satisfiability}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1995},
}
Figure