---
title: "Probabilistic Satisfiability: Logic-Based Algorithms and Phase Transition"
authors:
  - "Marcelo Finger"
  - "Glauber De Bona"
doi: "10.5591/978-1-57735-516-8/IJCAI11-096"
url: "https://ijcai.org/proceedings/2011/96"
pdf: "https://ijcai.org/proceedings/2011/0096.pdf"
venue: "Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence"
year: 2011
pages: "528-532"
track: ""
keywords:
---

# Probabilistic Satisfiability: Logic-Based Algorithms and Phase Transition

Marcelo Finger, Glauber De Bona

*Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence*, pages 528-532. DOI: [10.5591/978-1-57735-516-8/IJCAI11-096](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.