The Complexity of Closed World Reasoning and Circumscription

Marco Cadoli, Maurizio Lenzerini

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.

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.