Easy Cases of Probabilistic Satisfiability

By K. A. Andersen, D. Pretolani. 2001

28 citations recorded by the source corpus.

The Probabilistic Satisfiability problem (PSAT) can be considered as a probabilistic counterpart of the classical SAT problem. In a PSAT instance, each clause in a CNF formula is assigned a probability of being true; the problem consists in checking the consistency of the assigned probabilities. Actually, PSAT turns out to be computationally much harder than SAT, e.g., it remains difficult for some classes of formulas where SAT can be solved in polynomial time. A column generation approach has been proposed in the literature, where the pricing sub-problem reduces to a Weighted Max-SAT problem on the original formula. Here we consider some easy cases of PSAT, where it is possible to give a compact representation of the set of consistent probability assignments. We follow two different approaches, based on two different representations of CNF formulas. First we consider a representation based on directed hypergraphs. By extending a well-known integer programming formulation of SAT and Max-SAT, we solve the case in which the hypergraph does not contain cycles; a linear time algorithm is provided for this case. Then we consider the co-occurrence graph associated with a formula. We provide a solution method for the case in which the co-occurrence graph is a partial 2-tree, and we show how to extend this result to partial k-trees with k>2.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Computer Networks and Communications, Probabilistic & Bayesian Methods, Statistical Learning Theory

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

In Computer Networks and Communications

In Probabilistic & Bayesian Methods

In Statistical Learning Theory

Citations in the corpus

Measuring and Improving Consistency in Pretrained Language Models (2021, background): “Consistency in knowledge bases (KBs) has been studied in theoretical frameworks in the context of the satisfiability problem and KB construction, and efficient algorithms for detecting inconsistencies in KBs have been proposed (Hansen and Jaumard, 2000; Andersen and Pretolani, 2001).”
Measuring Inconsistency in Probabilistic Knowledge Bases (2009, background): “Furthermore the authors of (Hansen and Jaumard, 1996; Andersen and Pretolani, 2001) are mainly interested in efficient algorithms for determining whether a knowledge base is inconsistent and not to what degree.”
Enriching a Model's Notion of Belief using a Persistent Memory (2021, methodology): “In the area of formal knowledge-bases (KBs), efficient algorithms have been developed for detecting, measuring, and resolving inconsistency (Hansen and Jaumard, 2000; Andersen and Pretolani, 2001; Thimm, 2009; Muiño, 2011; Thimm, 2013).”
A Review on Language Models as Knowledge Bases (2022, background): “detect inconsistencies in KBs (Andersen and Pretolani, 2001) so such conflicts can be easily resolved, while other work aimed at quantifying the degree of which inconsistency arises in KBs (Picado-Muiño, 2011).”