NP-containment for the coherence test of assessments of conditional probability: a fuzzy logical approach

In this paper we investigate the problem of testing the coherence of an assessment of conditional probability following a purely logical setting. In particular we will prove that the coherence of an assessment of conditional probability χ can be characterized by means of the logical consistency of a suitable theory T _χ defined on the modal-fuzzy logic FP _k (RŁ_Δ) built up over the many-valued logic RŁ_Δ. Such modal-fuzzy logic was previously introduced in Flaminio (Lecture Notes in Computer Science, vol. 3571, 2005) in order to treat conditional probability by means of a list of simple probabilities following the well known (smart) ideas exposed by Halpern (Proceedings of the eighth conference on theoretical aspects of rationality and knowledge, pp 17–30, 2001) and by Coletti and Scozzafava (Trends Logic 15, 2002). Roughly speaking, such logic is obtained by adding to the language of RŁ_Δ a list of k modalities for “probably” and axioms reflecting the properties of simple probability measures. Moreover we prove that the satisfiability problem for modal formulas of FP _k (RŁ_Δ) is NP-complete. Finally, as main result of this paper, we prove FP _k (RŁ_Δ) in order to prove that the problem of establishing the coherence of rational assessments of conditional probability is NP-complete.