ML Anthology

Probabilistic Satisfiability: Logic-Based Algorithms and Phase Transition

Marcelo Finger, Glauber De Bona
IJCAI 2011 pp. 528-533
doi:10.5591/978-1-57735-516-8/IJCAI11-096 /ijcai/2011/finger2011ijcai-probabilistic/

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.

PDF IJCAI Semantic Scholar

Cite

Text

Finger and De Bona. "Probabilistic Satisfiability: Logic-Based Algorithms and Phase Transition." International Joint Conference on Artificial Intelligence, 2011. doi:10.5591/978-1-57735-516-8/IJCAI11-096

Markdown

[Finger and De Bona. "Probabilistic Satisfiability: Logic-Based Algorithms and Phase Transition." International Joint Conference on Artificial Intelligence, 2011.](https://mlanthology.org/ijcai/2011/finger2011ijcai-probabilistic/) doi:10.5591/978-1-57735-516-8/IJCAI11-096

BibTeX

@inproceedings{finger2011ijcai-probabilistic,
  title     = {{Probabilistic Satisfiability: Logic-Based Algorithms and Phase Transition}},
  author    = {Finger, Marcelo and De Bona, Glauber},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year      = {2011},
  pages     = {528-533},
  doi       = {10.5591/978-1-57735-516-8/IJCAI11-096},
  url       = {https://mlanthology.org/ijcai/2011/finger2011ijcai-probabilistic/}
}