Nobuhiro Yugam

IJCAI 1995

TL;DR

This paper provides a statistical analysis of the Davis-Putnam procedure (DP) for solving Boolean Satisfiability (SAT) problems, focusing on the "fixed clause length model." It offers theoretical predictions for SAT's probability and the DP's average-case complexity for both satisfiability checking and finding all solutions, which largely align with empirical observations.

What Problem Does This Paper Address?

Boolean Satisfiability (SAT) is a fundamental problem in computer science, particularly in Artificial Intelligence, due to its connection to automated reasoning and its use as a benchmark for constraint satisfaction algorithms. While SAT is known to be NP-complete (meaning worst-case solutions can be exponentially slow), understanding its average-case behavior is crucial for practical applications. Previous work had shown DP could be efficient under certain formula distribution models, but the "fixed clause length model" (where all clauses have a fixed number of literals) presented a more challenging scenario. This paper aims to provide a theoretical analysis of DP's average-case performance on this specific, important distribution model, investigating how its complexity varies with the density of clauses relative to variables.

Methods

The paper analyzes the Davis-Putnam procedure (DP), a classic tree-search algorithm for SAT. A simplified version, SDP (Davis-Putnam without explicit satisfiability checking at each step), is used for easier analysis. The core of the method involves developing recursive formulas to calculate probabilities related to the DP's execution:

  • Probabilities of clause states: Analyzing the likelihood of clauses becoming empty (unsatisfiable) or unit (containing only one literal) as variables are assigned values.
  • Unit Propagation analysis: Statistically modeling the effectiveness of the unit propagation rule, which significantly speeds up DP by forcing variable assignments based on unit clauses. This involves calculating probabilities of detecting empty clauses, satisfying clauses, or needing to branch.
  • Average-Case Complexity: Deriving recursive formulas for the expected number of SDP calls for both satisfiability checking and finding all solutions. These formulas depend on the number of bound variables and the number of variables assigned by unit propagation.
  • Probability of Satisfiability: Developing a model to predict the likelihood of a formula being satisfiable given a partial assignment of variables.

The analysis uses the "fixed clause length model" where formulas are generated by randomly selecting clauses of a fixed length (K) from a pool of possible clauses involving N variables.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis using a specific model of formula generation (the fixed clause length model) rather than empirical evaluation on predefined datasets.

Key Insights and Ideas

  • The "50% Satisfiable Point" is Critical: The paper confirms and theoretically explains the observed phenomenon that SAT problem difficulty (and DP's complexity) peaks around the point where approximately 50% of formulas are satisfiable. This "phase transition" is a well-known characteristic of random k-SAT instances.
  • Unit Propagation is Key, but its Effectiveness Varies: While unit propagation is the workhorse of DP, its statistical behavior (how many variables it assigns, how often it leads to contradictions) is highly dependent on the formula's structure and density.
  • Finding All Solutions is Harder: The analysis suggests that finding all satisfying assignments is generally more computationally expensive than simply determining if at least one exists.
  • Model Simplifications Matter: The authors acknowledge that approximations made in their statistical models (particularly for the probability of satisfiability) can lead to slight deviations from empirical results, especially in regions where these probabilities are crucial.

Key Results

  • Probability of Satisfiability: The theoretical predictions for the probability of a formula being satisfiable closely matched empirical results, with the statistical analysis identifying the 50% satisfiable point slightly higher than observed experimentally.
  • Complexity for Finding All Solutions: The theoretical predictions for the average-case complexity of finding all solutions showed excellent agreement with empirical results across various clause-to-variable ratios.
  • Complexity for Satisfiability Checking: The theoretical predictions for satisfiability checking complexity aligned well with empirical results above the 50% satisfiable point. Below this point, the theoretical complexity was slightly underestimated, attributed to an overestimation of the probability of satisfiability for partial assignments. The peak complexity was predicted to be around 20-25% lower than empirical observations.

Limitations and Future Work

  • Approximation in Probability of Satisfiability: The paper uses approximations for calculating the probability of satisfiability for partial assignments. This is identified as a source of discrepancy between theoretical and empirical results for satisfiability checking, particularly below the 50% satisfiable point.
  • Computational Cost: The recursive formulas for calculating probabilities and complexities are computationally intensive, especially for large N and M (number of variables and clauses), making direct computation impractical. The paper suggests approximations to mitigate this.
  • Future Work: The authors suggest further analysis could explore more sophisticated approximations or alternative models to improve accuracy, particularly for satisfiability checking. They also note that the analysis of unit propagation's effectiveness is a key area for future research.

Summary updated

BibTeX
@inproceedings{1995nobuhiro,
  title = {{Nobuhiro Yugam}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1995},
}
Figure