  Stochastic Boolean Satisfiability (SSAT) is a logical formalism to model
decision problems with uncertainty, such as Partially Observable Markov
Decision Process (POMDP) for verification of probabilistic systems. SSAT,
however, is limited by its descriptive power within the PSPACE complexity
class. More complex problems, such as the NEXPTIME-complete Decentralized POMDP
(Dec-POMDP), cannot be succinctly encoded with SSAT. To provide a logical
formalism of such problems, we extend the Dependency Quantified Boolean Formula
(DQBF), a representative problem in the NEXPTIME-complete class, to its
stochastic variant, named Dependency SSAT (DSSAT), and show that DSSAT is also
NEXPTIME-complete. We demonstrate the potential applications of DSSAT to
circuit synthesis of probabilistic and approximate design. Furthermore, to
study the descriptive power of DSSAT, we establish a polynomial-time reduction
from Dec-POMDP to DSSAT. With the theoretical foundations paved in this work,
we hope to encourage the development of DSSAT solvers for potential broad
applications.
