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.
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.
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:
- Existential branches (SAT) can be pruned as soon as a single satisfying assignment is found.
- 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