Initial Experiments in Stochastic Satisfiability

Abstract

Both satisfiability problems and probabilistic models are popular in artificial intelligence and computer science. This paper looks at the rich intersection between these two topics, opening the door for the use of satisfiability approaches in probabilistic domains. The paper examines a generic probabilistic satisfiability problem, which can function for probabilistic domains as Sat does for deterministic domains. Extending the analogy with Sat, the paper defines a DavisPutnam -Logemann-Loveland-style procedure for solving probabilistic satisfiability problems, and reports on a preliminary empirical exploration of the complexity of the algorithm for a collection of randomly generated probabilistic problems. The results exhibit the familiar easy-hardest-hard pattern for the difficulty of random Sat formulae. Special cases of the probabilistic satisfiability problem lie in different complexity classes, and one counterintuitive result is that the computational complexity and the empirica...