Introduction
In computational logic, there is a persistent trade-off between expressive power and computational efficiency. While standard Boolean Satisfiability (SAT) is effective for many deterministic problems, it struggles with uncertainty and complex information dependencies. Existing frameworks like Stochastic SAT (SSAT) handle uncertainty via random quantifiers but are limited to the PSPACE complexity class. Conversely, Dependency Quantified Boolean Formulas (DQBF) handle complex dependencies (NEXPTIME-complete) but lack native probabilistic modeling.
This paper introduces Dependency Stochastic Boolean Satisfiability (DSSAT), a new logical framework that bridges this gap. By merging the probabilistic reasoning of SSAT with the dependency structures of DQBF, DSSAT provides a succinct way to model high-complexity problems such as decentralized multi-agent systems (Dec-POMDPs) and probabilistic circuit design. The authors prove that the decision version of DSSAT is NEXPTIME-complete.
Formalism and Complexity
DSSAT extends the quantification structure of Boolean formulas by incorporating hybrid quantifiers. It utilizes random quantifiers ($\text{R}^p$), which define the probability of a variable being true, alongside existential quantifiers ($\exists$) that include explicit dependency sets.
Unlike standard logic, where a variable implicitly depends on all preceding variables, DSSAT employs Henkin quantifiers. This allows for the specification of exactly which random variables an existential variable "knows." This structure is crucial for modeling decentralized environments where agents have only partial information. The jump from PSPACE to NEXPTIME is driven entirely by these dependency sets; by restricting what an existential variable "sees," one can model decentralized coordination, which is computationally much harder than centralized control.
Key Insights and Applications
A primary strength of DSSAT is its inherent nature as an optimization problem. While DQBF is a "yes/no" decision problem, DSSAT is typically used to find the "maximum satisfying probability," making it more flexible for real-world engineering where the goal is the best possible solution under uncertainty.
Circuit Distillation and Modeling
The paper highlights a "distillation operation" to model noisy, probabilistic hardware. By adding auxiliary random inputs to an error-free circuit, one can represent gates that fail with a specific probability $p$. This is particularly useful for the synthesis of modern approximate computer chips.
Multi-Agent Planning
The authors establish a formal, polynomial-time reduction from Decentralized Partially Observable Markov Decision Processes (Dec-POMDPs) to DSSAT. This proves that complex multi-agent planning problems can be translated into compact DSSAT formulas, offering a unified language that subsumes SAT, QBF, SSAT, and DQBF.
Conclusion and Future Work
DSSAT provides a powerful theoretical foundation for modeling uncertainty in high-complexity domains. However, as a foundational work, it currently lacks dedicated high-performance solvers. The NEXPTIME-completeness also implies significant computational challenges, as even small problems could be incredibly difficult to solve in practice. Future research aims to adapt "clausal abstraction" techniques from DQBF and SSAT to develop the first generation of DSSAT solvers, potentially revolutionizing AI planning and formal verification.
Summary updated