View Related Documents

Abstract

Both probabilistic satisfiability (PSAT) and the check of coherence of probability assessment (CPA) can be considered as probabilistic counterparts of the classical propositional satisfiability problem (SAT). Actually, CPA turns out to be a particular case of PSAT; in this paper, we compare the computational complexity of these two problems for some classes of instances. First, we point out the relations between these probabilistic problems and two well known optimization counterparts of SAT, namely Max SAT and Min SAT. We then prove that Max SAT with unrestricted weights is NP-hard for the class of graph formulas, where Min SAT can be solved in polynomial time. In light of the aforementioned relations, we conclude that PSAT is NP-complete for ideal formulas, where CPA can be solved in linear time.

Keywords  probability - logic - CNF formulas - propositional satisfiability - directed graphs - ideal matrices

Fulltext Preview

Image of the first page of the fulltext document