Possibilistic logic: Complexity and algorithms (Q2752126)

This paper represents a chapter in Volume 5 of the Handbook of defeasible reasoning and uncertainty management systems. It contains a comprehensive study of algorithmic and complexity issues related to possibilistic logic. Section 1 of the paper introduces the main notions and problems. Section 2 recalls the basics of possibilistic theory, viz. a formal background of standard possibilistic logic (SPL). SPL, or necessity-valued fragment of possibilistic logic, although poorer than full possibilistic logic, is important because: (a) algorithmic issues are simpler and easily extendible to the full case, and (b) SPL is sufficient for modelling a preference order upon formulae, which is closely related to the nonmonotonic approach to preferential models and belief revision theory. Section 3 investigates algorithmic and complexity issues for the deduction problem in SPL. Several versions of the deduction problem are considered for a possibilistic extension of refutation by resolution. The complexity issues are restricted to the case of propositional necessity-valued logic. Section 4 discusses algorithms for possibilistic model finding, based on an extension of the well-known procedure of Davis and Putnam, also in the case of propositional SPL. Section 5 examines proof methods for an extended fragment of possibilistic logic, which handles both certainty-valued and possibility-valued statements. The final Section 6 concludes, pointing to related work such as fuzzy constraint satisfaction, possibilistic logic programming, and drowning-free variants of possibilistic logic. Nine important areas of applications of the discussed topics are emphasized.NEWLINENEWLINEFor the entire collection see [Zbl 0959.00013].