Generalized Probabilistic Satisfiability
Carlos Caleiro, Filipe Casal, Andreia Mordido · Electronic Notes in Theoretical Computer Science · 2017
We analyze a generalized probabilistic satisfiability problem ( GenPSAT ) which consists in deciding the satisfiability of linear inequalities involving probabilities of classical propositional formulas. GenPSAT is proved to be NP -complete and we present a polynomial reduction to Mixed-Integer Programming. Capitalizing on this translation, we implement and test a solver for the GenPSAT problem. As previously observed for many other NP -complete problems, we are able to detect a phase transition behaviour for GenPSAT .