Probabilistic Satisfiability: Logic-Based Algorithms and Phase Transition

Finger, Marcelo; De Bona, Glauber

doi:10.5591/978-1-57735-516-8/IJCAI11-096

Probabilistic Satisfiability: Logic-Based Algorithms and Phase Transition

Marcelo Finger, Glauber De Bona

Download BibTeX Cite

Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence. Pages 528-532.

https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-096

Abstract

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.

Marcelo Finger, and Glauber De Bona. 2011. Probabilistic Satisfiability: Logic-Based Algorithms and Phase Transition. In Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11. IJCAI, 528–532. https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-096

@inproceedings{ijcai2011p96,
  title     = {Probabilistic Satisfiability: Logic-Based Algorithms and Phase Transition},
  author    = {Finger, Marcelo and De Bona, Glauber},
  booktitle = {Proceedings of the Twenty-Second International Joint Conference on
               Artificial Intelligence, {IJCAI-11}},
  publisher = {AAAI Press/International Joint Conferences on Artificial Intelligence},
  editor    = {Toby Walsh},
  pages     = {528--532},
  year      = {2011},
  month     = {7},
  doi       = {10.5591/978-1-57735-516-8/IJCAI11-096},
  url       = {https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-096},
}

TY  - CPAPER
TI  - Probabilistic Satisfiability: Logic-Based Algorithms and Phase Transition
AU  - Finger, Marcelo
AU  - De Bona, Glauber
T2  - Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11
PB  - AAAI Press/International Joint Conferences on Artificial Intelligence
PY  - 2011
SP  - 528
EP  - 532
DO  - 10.5591/978-1-57735-516-8/IJCAI11-096
UR  - https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-096
ER  -