Initial Experiments in Stochastic Satisfiability

Michael L. Littman

Abstract

Stochastic Satisfiability (SSAT) provides a formal framework for reasoning under uncertainty by combining existential and randomized quantifiers. This paper presents the evalssat algorithm, a generalization of the DPLL procedure, and evaluates its performance on random 3-CNF formulas. Experimental results reveal a "complexity paradox" where problems that are theoretically harder (PSPACE-complete) can be empirically easier than those in lower complexity classes like PP, highlighting the impact of pruning heuristics in probabilistic search spaces.

Introduction: Bridging Logic and Probability

In the late 1990s, artificial intelligence research was often divided between deterministic logic-based planning and probabilistic modeling. Standard Boolean satisfiability (SAT) is highly efficient for deterministic tasks but lacks the expressive power to handle "chance" or environmental uncertainty.

The authors address this gap by formalizing Stochastic Satisfiability (SSAT). In this framework, variables are either "choice" variables (existential quantifiers $\exists$) controlled by an agent or "chance" variables (randomized quantifiers $\text{y}$) determined by nature. The objective is to find a sequence of choices that ensures the probability of formula satisfaction exceeds a threshold $\theta$. This hierarchy unifies several problem classes, ranging from NP to PSPACE.

Table 1: Classification of satisfiability and planning problems across complexity classes.

The evalssat Algorithm

The core contribution is evalssat, an extension of the Davis-Putnam-Logemann-Loveland (DPLL) procedure. To handle the probabilistic nature of SSAT, the algorithm incorporates several key innovations:

  • Generalized Quantifiers: It recursively evaluates both $\exists$ and $\text{y}$ variables.
  • Probabilistic Unit Resolution: Simplifies the expected value calculation when a chance variable appears alone in a clause.
  • Threshold Pruning: Similar to Alpha-Beta pruning, the solver maintains lower ($\theta_l$) and upper ($\theta_h$) bounds. If it becomes mathematically certain that the target threshold cannot be met, the branch is pruned.
  • Purification: Variables appearing with only one polarity are fixed to their satisfying value, avoiding unnecessary search.

Empirical Hardness and the Complexity Paradox

The experiments confirmed that stochastic satisfiability follows the "easy-hard-easy" phase transition pattern seen in standard SAT. However, a surprising "complexity paradox" emerged regarding the relative difficulty of different problem classes.

Figure 1: Comparison of empirical work (recursive calls) for different stochastic satisfiability variants at n=20.

While SSAT is theoretically PSPACE-complete (making it "harder" than the PP-complete MAJSAT on paper), MAJSAT proved to be the most difficult to solve empirically. This is largely due to Pruning Asymmetry:

  1. Existential branches (SAT) can be pruned as soon as a single satisfying assignment is found.
  2. Randomized branches (MAJSAT/SSAT) often require exploring both "true" and "false" paths to compute an exact probability, making them much harder to prune.

The empirical difficulty ranking was found to be: SAT < E-MAJSAT < SSAT < MAJSAT. Additionally, the peak difficulty for MAJSAT occurs at a much lower clause-to-variable ratio ($m/n \approx 2$) than for standard SAT ($m/n \approx 4.3$).

Conclusion and Future Directions

This work demonstrates that theoretical complexity does not always dictate empirical performance in probabilistic reasoning. The effectiveness of threshold pruning is highly sensitive to the problem type and the specific probability threshold used. Future research will focus on advanced variable-ordering heuristics and scaling these experiments to larger variable sets where phase transitions become more pronounced.

Summary updated

Abstract

This paper looks at the rich intersection between satisfiability problems and probabilistic models, opening the door for the use of satisfiability approaches in probabilistic domains. A generic stochastic satisfiability problem is examined, which can function for probabilistic domains as SAT does for deterministic domains. The paper defines a Davis-Putnam-Logemann-Loveland-style procedure for solving stochastic satisfiability problems, and reports on a preliminary empirical exploration of the complexity of the algorithm for a collection of randomly generated probabilistic problems. The results exhibit the familiar easyhardest-hard pattern for the difficulty of random SAT formulae. Special cases of the stochastic satisfiability problem lie in different complexity classes, and one counterintuitive result is that the computational complexity and the empirical complexity of the problems examined do not track each other exactly-problems in the hardest complexity class are not the hardest to solve.
BibTeX
@inproceedings{littman1999initial,
  author = {Michael L. Littman},
  title = {{Initial Experiments in Stochastic Satisfiability}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1999},
}
Figure