The Complexity of 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. We present a detailed analysis of the computational complexity of the different forms of closed world reasoning for various fragments of propositional logic. The analysis allows us to draw a complete picture of the tractability/intractability frontier for such a form of nonmonotonic reasoning. We also discuss how to use our results in order to characterize the computational complexity of other problems related to nonmonotonic inheritance, diagnosis, and default reasoning.

Authors

• Marco Cadoli Andrea Giovanardi

Keywords

No keywords are indexed for this paper.