The complexity of propositional closed world reasoning and circumscription

摘要

Closed world reasoning is a common nonmonotonic technique that allows for dealing with negative information in knowledge and data bases. Several forms of closed world reasoning have been proposed in the literature, ranging from the closed world assumption, introduced in the context of data bases, to the extended closed world assumption, which is equivalent to circumscription. The aim of this paper is to present a detailed analysis of the computational complexity of the different forms of closed world reasoning for various fragments of propositional logic. Such an analysis allows us to draw a complete picture of the boundary between tractability and intractability of such a form of nonmonotonic reasoning. We also discuss how to use our results in order to characterize the computational complexity of other nonmonotonic reasoning problems, namely nonmonotonic inheritance, diagnosis, and default reasoning.