A Sharp Leap from Quantified Boolean Formula to Stochastic Boolean Satisfiability Solving

Pei-Wei Chen, Yu-Ching Huang, Jie-Hong R. JiangAAAI 2021 · DOI

Abstract

Stochastic Boolean Satisfiability (SSAT) extends Boolean Satisfiability (SAT) with randomized quantifiers, making it a powerful tool for modeling uncertainty but also computationally demanding (PSPACE-complete). We present ClauSSat, a novel solver that adapts clause selection techniques from Quantified Boolean Formula (QBF) solving to the SSAT domain. By leveraging off-the-shelf SAT solvers and a new randomized level pruning technique based on matrix containment, ClauSSat achieves significant improvements in search space pruning. Experimental results on 318 benchmarks demonstrate that ClauSSat outperforms existing general-purpose solvers in both coverage and memory efficiency, solving 188 instances while maintaining a peak memory footprint of only 2.4 GB.

Introduction

In automated reasoning, Boolean Satisfiability (SAT) determines if a formula can be made true. Quantified Boolean Formula (QBF) extends this with existential ($\exists$) and universal ($\forall$) quantifiers. Stochastic Boolean Satisfiability (SSAT) introduces "randomized" quantifiers, where variables are true with a specific probability. This makes SSAT ideal for modeling "games against nature," such as probabilistic planning and belief network inference. However, SSAT is PSPACE-complete and requires model counting (#SAT), which is notoriously expensive. ClauSSat bridges the gap between logic-based reasoning and probabilistic uncertainty by adapting QBF "clause selection" techniques to efficiently prune the search space.

Methods

ClauSSat treats SSAT solving as a search through "clause selections." Instead of exhaustive variable assignment, it tracks which clauses are satisfied at different quantification levels.

Black-box Integration

ClauSSat is designed with a modular architecture, utilizing off-the-shelf SAT solvers and model counters as subroutines. This "black-box" approach ensures that ClauSSat benefits from continuous advancements in underlying SAT technology without requiring fundamental redesigns.

Randomized Level Pruning

A core innovation is the Matrix Containment Property. This property posits that if the requirements of one sub-problem are a subset of another, its satisfaction probability must be higher. This simple logical truth allows the solver to aggressively prune redundant calculations at both existential and randomized levels.

Search Enhancements

The solver integrates several advanced techniques to navigate the search tree:

  • Cube Distribution: Handles multiple clauses simultaneously to speed up search.
  • Maximal Clause Pruning: Reduces the number of clauses considered during the search process.
  • Non-chronological Backtracking: Enables the solver to skip irrelevant branches of the search tree, improving overall efficiency.

Experimental Results

The performance of ClauSSat was evaluated against 318 SSAT formulas across 23 families, including converted QBFs and domain-specific benchmarks like hardware verification and probabilistic planning.

Table 1: Benchmark statistics and performance comparison between ClauSSat, DC-SSAT, and {erSSAT, reSSAT}.

As shown in Table 1, ClauSSat demonstrated superior performance across a wide range of benchmarks. Out of 318 formulas, ClauSSat exactly solved 188 and provided the tightest known bounds for an additional 98. In contrast, the previous leading general-purpose solver, DC-SSAT, solved 169 instances.

A standout feature of ClauSSat is its memory efficiency. While DC-SSAT required up to 32.1 GB of memory, ClauSSat's peak memory usage was only 2.4 GB. Furthermore, ClauSSat successfully handled complex multi-level formulas that specialized two-level solvers like erSSAT and reSSAT could not process.

Discussion

The success of ClauSSat stems from its focus on structural abstraction over simple enumeration. By using selection variables to represent clause status, the solver reasons about the problem's underlying logic. The modular architecture also proves that a well-designed wrapper around high-performance SAT engines can outperform monolithic, specialized solvers. However, ClauSSat currently lacks structural decomposition strategies, which makes it slower on highly decomposable benchmarks like "Sand-Castle."

Conclusion

ClauSSat represents a significant advancement in SSAT solving by successfully porting QBF techniques to the stochastic domain. Future work will focus on integrating "divide-and-conquer" structural decomposition and exploring approximate model counting to provide fast, high-confidence bounds for even larger problem instances.

Summary updated

BibTeX
@inproceedings{chen2021sharp,
  author = {Pei-Wei Chen and Yu-Ching Huang and Jie-Hong R. Jiang},
  title = {{A Sharp Leap from Quantified Boolean Formula to Stochastic Boolean Satisfiability Solving}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.1609/aaai.v35i5.16486},
}
Figure