Abstract
SharpSSAT is a high-performance Stochastic Boolean Satisfiability (SSAT) solver that introduces the capability to generate "Skolem-function witnesses"—actual strategies that explain how to achieve a calculated probability. By integrating advanced model-counting techniques like clause learning and component caching, it not only solves more problems than current state-of-the-art solvers but also produces significantly more compact decision-making strategies.
Introduction: Decision-Making Under Uncertainty
Stochastic Boolean Satisfiability (SSAT) is a powerful framework for decision-making under uncertainty. While a standard SAT solver asks "Is there a solution?", an SSAT solver asks "What is the maximum probability that this formula is satisfied, given some variables are random and others are under our control?"
The major gap in the field has been witness generation. Existing solvers are effective at calculating probabilities (e.g., "You have an 85% chance of success"), but they often fail to provide the strategy to achieve that result. In practical applications like robotics planning or network access control, the strategy (represented as Skolem functions) is often more critical than the probability itself. SharpSSAT addresses this by providing both the "what" and the "how."
Methods: Two-Phase Witness Generation
SharpSSAT is built upon the architecture of the model counter SharpSAT, enhanced with clause learning and pure literal detection to prune the search space. The core innovation lies in its two-phase witness generation process:
- Trace Recording: As the solver explores the search tree, it records decisions in a Directed Acyclic Graph (DAG). To manage memory, the solver eliminates redundant "and-nodes" and uses reference counting to prune dead branches.
- Extraction: Once the maximum probability is found, the solver traverses the DAG in topological order to construct Skolem functions for every existential variable.
This top-down approach allows SharpSSAT to prune irrelevant information early, resulting in much smaller strategy circuits compared to the bottom-up approaches used by competing solvers.
Experimental Setup
The researchers evaluated SharpSSAT using a benchmark set of 357 SSAT problems across 20 different families, including games (Connect2, Tiger), logic circuits (Adder, MPEC), and planning (Robot, Planning-CTE). The set includes both two-level and complex multi-level quantified formulas.
Key Results and Performance
SharpSSAT demonstrates superior solving capacity and efficiency compared to existing state-of-the-art solvers.
- Solving Capacity: SharpSSAT solved 232 out of 357 instances, outperforming ElimSSAT (226), ClauSSat (196), Prime (186), and DC-SSAT (177).
- Witness Compactness: SharpSSAT produced strategies that were often orders of magnitude smaller than those produced by ClauSSat, measured in AIG node counts.
- Overhead: Generating a witness adds negligible runtime overhead, though it typically requires approximately 2x the memory of a non-witnessing run to store the trace.
Limitations and Future Work
While SharpSSAT optimizes trace representation, storing the entire solving history in a DAG remains memory-intensive for extremely large instances. Future work aims to optimize "existential components" using Conflict-Driven Clause Learning (CDCL) and explore knowledge compilation techniques like d-DNNFs to represent the search space even more efficiently for witness extraction.
Summary updated