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.