| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 4950013 | Electronic Notes in Theoretical Computer Science | 2017 | 18 Pages |
Abstract
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Carlos Caleiro, Filipe Casal, Andreia Mordido,