The coherence of Łukasiewicz assessments is NP-complete

详细信息    查看全文

• 作者：Simone Bova ; Tommaso Flaminio
• 关键词：De Finetti’ ; s coherence criterion ; Infinite-valued Ł ; ukasiewicz logic ; NP-completeness ; SMV-algebras ; Probabilistic Kripke models
• 刊名：International Journal of Approximate Reasoning
• 出版年：2010
• 出版时间：February 2010
• 年：2010
• 卷：51
• 期：3
• 页码：294-304
• 全文大小：252 K

文摘

The problem of deciding whether a rational assessment of formulas of infinite-valued Łukasiewicz logic is coherent has been shown to be decidable by Mundici [1] and in PSPACE by Flaminio and Montagna [10]. 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 Flaminio and Montagna in [9].