Initial Experiments in Stochastic Satisfiability

This paper looks at the rich intersection between satisfiability problems and probabilistic models, openingthe door for the use of satisfiability approaches in probabilistic domains. A generic stochastic satisfiability problemis examined, whichcan function for probabilistic domains as SAT does for deterministic domains. Thepaper defines a Davis-Putnam-Logemann-Loveland-style procedurefor solving stochastic satisfiability problems, and reports on a preliminary empirical exploration of the complexity of the algorithm for a collection of randomlygenerated probabilistic problems. Theresults exhibit the familiar easyhardest-hard pattern for the difficulty of random SAT formulae. Special cases of the stochastic satisfiability problem lie in different complexity classes, and onecounterintuitive result is that the computational complexity and the empirical complexity of the problems examineddo not track each other exactly--problems in the hardest complexityclass are not the hardest to solve.

Authors

• Michael L. Littman
• Duke University

Keywords

No keywords are indexed for this paper.