×

The coherence of Łukasiewicz assessments is NP-complete. (English) Zbl 1201.68117

Summary: The problem of deciding whether a rational assessment of formulas of infinite-valued Łukasiewicz logic is coherent has been shown to be decidable by D. Mundici [Theor. Comput. Sci. 52, 145–153 (1987; Zbl 0639.03042)] and in PSPACE by T. Flaminio and F. Montagna [J. Log. Comput., “Models for many-valued probabilistic reasoning”, doi:10.1093/logcom/exp013]. We settle its computational complexity proving an NP-completeness result. We then obtain NP-completeness results for the satisfiability problem of certain many-valued probabilistic logics introduced by T. Flaminio and F. Montagna in [Int. J. Approx. Reasoning 50, No. 1, 138–152 (2009; Zbl 1185.06007)].

MSC:

68T37 Reasoning under uncertainty in the context of artificial intelligence
03B50 Many-valued logic
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68Q25 Analysis of algorithms and problem complexity
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Chang, C. C., Algebraic analysis of many-valued logics, Trans. Amer. Math. Soc., 88, 467-490 (1958) · Zbl 0084.00704
[2] Cignoli, R.; D’Ottaviano, I. M.L.; Mundici, D., Algebraic foundations of many-valued reasoning (2000), Kluwer · Zbl 0937.06009
[3] de Finetti, B., Sul Significato Soggettivo della Probabilità, Fundamenta Mathematicae, 17, 298-329 (1931) · JFM 57.0608.07
[4] de Finetti, B., La Prévision: ses Lois Logiques, ses Sources Subjectives, Annales de l’Institut H. Poincaré, 7, 1-68 (1937) · JFM 63.1070.02
[5] de Finetti, B., Theory of Probability, vol. 1 (1974), Wiley
[6] Edwald, G., Combinatorial Convexity and Algebraic Geometry (1996), Springer
[7] T. Flaminio, A Fuzzy-Modal Approach to Probability: from Crisp to Fuzzy Events. Ph.D. Thesis, University of Siena, 2006.; T. Flaminio, A Fuzzy-Modal Approach to Probability: from Crisp to Fuzzy Events. Ph.D. Thesis, University of Siena, 2006.
[8] Flaminio, T.; Godo, L., A logic for reasoning about the probability of fuzzy events, Fuzzy Sets and Systems, 158, 625-638 (2007) · Zbl 1116.03018
[9] Flaminio, T.; Montagna, F., MV-algebras with internal states and probabilistic fuzzy logics, International Journal of Approximate Reasoning, 50, 138-152 (2009) · Zbl 1185.06007
[10] T. Flaminio, F. Montagna, Models for many-valued probabilistic reasoning, Journal of Logic and Computation, doi:10.1093/logcom/exp013.; T. Flaminio, F. Montagna, Models for many-valued probabilistic reasoning, Journal of Logic and Computation, doi:10.1093/logcom/exp013. · Zbl 1237.06005
[11] B. Gerla, Many-valued Logics of Continuous t-norms and Their Functional Representation, Ph.D. Thesis, Univerity of Milan, 2001.; B. Gerla, Many-valued Logics of Continuous t-norms and Their Functional Representation, Ph.D. Thesis, Univerity of Milan, 2001.
[12] Hájek, P., Metamathematics of Fuzzy Logic (1998), Kluwer · Zbl 0937.03030
[13] Hájek, P., Complexity of fuzzy probabilistic logics II, Fuzzy Sets and Systems, 158, 23, 2605-2611 (2007) · Zbl 1124.03008
[14] Kôpka, F.; Chovanec, F., D-posets, Math. Slovaca, 44, 21-34 (1994) · Zbl 0789.03048
[15] Kühr, J.; Mundici, D., De Finetti theorem and Borel states in \([0, 1]\)-valued algebraic logic, International Journal of Approximate Reasoning, 46, 3, 605-616 (2007) · Zbl 1189.03076
[16] McNaughton, R., A theorem about infinite-valued sentential logic, J. Symb. Log., 16, 1-13 (1951) · Zbl 0043.00901
[17] Montagna, F., Subreducts of MV-algebras with product and product residuation, Algebra Universalis, 53, 109-137 (2005) · Zbl 1086.06010
[18] Montagna, F.; Panti, G., Adding structure to MV-algebras, Journal of Pure and Applied Algebra, 164, 365-387 (2001) · Zbl 0992.06012
[19] Mundici, D., Satisfiability in many-valued sentential logic is NP-complete, Theoretical Computer Science, 52, 145-153 (1987) · Zbl 0639.03042
[20] Mundici, D., A constructive proof of McNaughton’s theorem in infinite-valued logic, J. Symb. Log., 59, 2, 596-602 (1994) · Zbl 0807.03012
[21] Mundici, D., Averaging the truth-value in Łukasiewicz logic, Studia Logica, 55, 1, 113-127 (1995) · Zbl 0836.03016
[22] Mundici, D., Bookmaking over infinite-valued events, International Journal of Approximate Reasoning, 43, 223-240 (2006) · Zbl 1123.03011
[23] Paris, J. B., The uncertain reasoner’s companion. The uncertain reasoner’s companion, A Mathematical Perspective (1994), Cambridge University Press · Zbl 0838.68104
[24] J.B. Paris, A note on the Dutch book method, in: Proceedings of the Second International Symposium on Imprecise Probabilities and their Applications (ISIPTA), 2001, pp. 301-306.; J.B. Paris, A note on the Dutch book method, in: Proceedings of the Second International Symposium on Imprecise Probabilities and their Applications (ISIPTA), 2001, pp. 301-306.
[25] Schrijver, A., Theory of Linear and Integer Programming (1998), Wiley · Zbl 0970.90052
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.