Lifting (D)QBF Preprocessing and Solving Techniques to (D)SSAT

Che Cheng, Jie-Hong R. JiangAAAI 2023 · DOI

Introduction

Dependency Stochastic Boolean Satisfiability (DSSAT) represents a significant advancement in logic modeling, extending Stochastic SAT (SSAT) by allowing existential variables to depend on specific subsets of randomized variables via Henkin quantifiers. This capability is crucial for modeling complex systems with non-linear dependencies and probabilistic uncertainty, such as partial equivalence checking in hardware design. However, DSSAT is NEXPTIME-hard, and until recently, no practical solvers or standalone preprocessors existed. This paper introduces a framework to solve DSSAT by "lifting" established techniques from the Quantified Boolean Formula (QBF) and Dependency QBF (DQBF) domains.

Methodology

The proposed approach involves two primary contributions: a dependency elimination algorithm and a suite of lifted preprocessing techniques.

Dependency Elimination

To leverage existing SSAT solvers, the authors developed an algorithm to transform DSSAT formulas into standard SSAT formulas. This process eliminates complex dependency sets, making the problems solvable by state-of-the-art SSAT engines.

Preprocessing Techniques

The authors adapted the DQBF preprocessor HQSpre to create DSSATpre. This involved modifying core techniques to account for the probabilistic weights of randomized variables. Key findings include:

  • Unit Propagation and Backbones: These were extended to maintain the probability weight of eliminated variables.
  • Equivalent Literals: A method was developed to merge randomized variables while deriving a mathematically sound new probability ($p_v$).
  • The "No-Go" Theorem: Crucially, the authors proved that Universal Reduction, a cornerstone of QBF solving, is unsound for DSSAT. Randomized variables contribute to the overall probability even if they are the sole reason for a clause's falsification, meaning they cannot be simply discarded.
Applicability of lifted preprocessing techniques to DSSAT.

Experimental Setup

Since no native DSSAT benchmarks existed, the authors reinterpreted 2,316 instances from the Biere and Scholl DQBF suites. Universal variables were converted into randomized variables with a probability of 0.5, transforming logic-checking problems into probabilistic design-equivalence challenges.

Results and Performance Analysis

The integration of DSSATpre with existing SSAT solvers yielded the first practical results for these benchmarks. Preprocessing proved to be a critical component, significantly reducing the computational burden on the main solver phase.

Impact of individual preprocessing techniques on solver PAR2 scores.

As illustrated in the performance analysis, full preprocessing reduced the PAR2 score (a runtime metric penalizing timeouts) for the DC-SSAT solver by 25.5%. The study also highlighted solver-specific sensitivities: ElimSSAT relies heavily on subsumption techniques, while ClauSSat benefits more from resolution-based simplification. Notably, the preprocessor was effective enough to solve 30 instances during the preprocessing phase alone, before the main solver was even invoked.

Conclusion

This research establishes the first practical foundation for DSSAT solving by successfully lifting (D)QBF techniques. While the current framework relies on elimination to standard SSAT, future work will focus on developing native DSSAT solvers that handle Henkin quantifiers directly and identifying sound reduction techniques to replace the unsound Universal Reduction.

Summary updated

BibTeX
@inproceedings{cheng2023lifting,
  author = {Che Cheng and Jie-Hong R. Jiang},
  title = {{Lifting (D)QBF Preprocessing and Solving Techniques to (D)SSAT}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2023},
  doi = {10.1609/aaai.v37i4.25504},
}

Loading related content...

Figure