AAAI Publications, Twenty-Second International Joint Conference on Artificial Intelligence

Font Size: 
Probabilistic Satisfiability: Logic-Based Algorithms and Phase Transition
Marcelo Finger, Glauber De Bona

Last modified: 2011-06-28


In this paper, we study algorithms for probabilistic satisfiability (PSAT), an NP-complete problem, and their empiric complexity distribution. We define a PSAT normal form, based on which we propose two logic-based algorithms: a reduction of normal form PSAT instances to SAT, and a linear-algebraic algorithm with a logic-based column generation strategy. We conclude that both algorithms present a phase transition behaviour and that the latter has a much better performance.

Full Text: PDF