Unifying Decision and Function Queries in Stochastic Boolean Satisfiability

Yu-Wei Fan, Jie-Hong R. JiangAAAI 2024 · DOI

Abstract

Stochastic Boolean Satisfiability (SSAT) provides a robust framework for decision-making under uncertainty. However, traditional SSAT is limited by its inability to handle nested probabilistic reasoning efficiently. This paper introduces SSAT($\Theta$), a new formalism that incorporates threshold quantifiers to unify decision and function queries. This extension allows for the succinct encoding of complex problems like parameter synthesis and probabilistic model checking while remaining within the PSPACE complexity class. We present ClauSSat($\Theta$), the first solver designed for this logic, and evaluate its performance across several benchmark families.

Introduction

Stochastic Boolean Satisfiability (SSAT) models problems where variables are either existential (controlled by a decision-maker) or randomized (governed by probability distributions). A significant limitation of standard SSAT is its reliance on a single, global threshold for the entire formula. This constraint makes it difficult to model scenarios requiring nested probabilistic reasoning, such as finding system parameters that guarantee a property holds with a specific probability.

To address this, the authors introduce SSAT($\Theta$), which adds "threshold quantifiers" ($\Theta^{\triangleright p}$) to the standard SSAT prefix. This allows the framework to evaluate whether the probability of a sub-formula meets a specified threshold $p$, returning a Boolean value. This unification of decision and function queries enables the encoding of problems in the Counting Hierarchy without increasing the computational complexity beyond PSPACE-complete.

Methodology

The core of this approach is the Threshold Quantifier ($\Theta^{\triangleright p}$). In the formula prefix, $\Theta^{\triangleright p}$ acts as a gate: if the probability of the subsequent sub-formula satisfies the condition $\triangleright p$, the quantifier evaluates to true.

To implement this logic, the authors developed ClauSSat($\Theta$), an extension of the state-of-the-art ClauSSat solver. Key technical contributions include:

  1. Normal Form Definition: Establishing rules for quantifier reordering to minimize redundancy.
  2. Recursive Solving: Utilizing "quantification levels" to partition variables and apply recursive techniques.
  3. BPCTL Encoding: Providing a formal translation from Bounded Probabilistic Computation Tree Logic (BPCTL) into SSAT($\Theta$), facilitating the verification of probabilistic systems.

Experimental Evaluation

The solver was evaluated using two primary benchmark sets: parameter synthesis for the Crowds protocol and extended SSAT benchmarks.

Parameter Synthesis

The Crowds protocol benchmarks involve finding crowd sizes that maximize sender anonymity over $k$ time steps. As shown in Figure 1, the solver successfully handled instances with over 11,000 clauses and 4,000 variables. However, run times increased significantly with the number of time steps $k$, eventually leading to timeouts (TO).

Experimental results for parameter synthesis on the Crowds protocol, showing formula size and run times across different ranges and time steps.

SSAT Extensions

The authors also tested the solver on modified versions of standard SSAT families (tlc, gttt, Robot, and stracomp) by inserting threshold quantifiers.

Performance comparison between standard SSAT and SSAT($\Theta$) across various benchmark families.

As illustrated in Figure 2, the introduction of threshold quantifiers generally increases computational difficulty. For instance, in the stracomp family, problems that standard SSAT solved in less than a second became timeouts for SSAT($\Theta$), highlighting the performance trade-offs associated with increased expressiveness.

Discussion and Future Work

SSAT($\Theta$) represents a significant step in unifying different types of probabilistic queries. By treating thresholds as quantifiers, the gap between finding probabilities (function queries) and checking thresholds (decision queries) is bridged. While ClauSSat($\Theta$) is the first of its kind, the experiments reveal challenges in scalability and pruning. Specifically, certain quantifier sequences (Randomized-Threshold-Randomized) break standard optimization techniques, necessitating new pruning strategies.

Future work will focus on improving solver scalability for large BPCTL models and exploring extensions to Dependency SSAT (DSSAT) to handle non-linear variable dependencies.

Reference: Fan, Y.-W., & Jiang, J.-H. R. (2024). Unifying Decision and Function Queries in Stochastic Boolean Satisfiability. Proceedings of the AAAI Conference on Artificial Intelligence (AAAI-24).

Summary updated

BibTeX
@inproceedings{fan2024unifying,
  author = {Yu-Wei Fan and Jie-Hong R. Jiang},
  title = {{Unifying Decision and Function Queries in Stochastic Boolean Satisfiability}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2024},
  doi = {10.1609/aaai.v38i8.28637},
}
Figure