PhD Seminar: From SAT to Stochastic SAT

Speaker: Ricardo Salmon, PhD Candidate

Stochastic satisfiability (SSAT) problems are an extension of SAT problems that is PSPACE-complete and in the same complexity class as quantified Boolean formula (QBF) and partially observable Markov decision processes (POMDPs).

We show how to extend techniques from SAT into a stochastic solver called Prime, that solves probabilistic inference and POMDP problems. Similar to SAT and other NP-hard problems where a lot of research has been invested, we hope to encourage further research into SSAT. The results show that our solver is able to tackle large problems and is very competitive.