Name
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. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1016/j.entcs.2017.04.004 | Electronic Notes in Theoretical Computer Science |
Keywords | DocType | Volume |
Probabilistic Satisfiability,GenPSAT,Mixed-Integer Programming,Phase Transition | Journal | 332 |
ISSN | Citations | PageRank |
1571-0661 | 0 | 0.34 |
References | Authors | |
0 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Carlos Caleiro | 1 | 6 | 3.42 |
| Filipe Casal | 2 | 1 | 2.40 |
| Andreia Mordido | 3 | 0 | 2.37 |