The complexity of closed world reasoning and circumscription
Marco Cadoli, Maurizio Lenzerini · 1990
Closed world reasoning is a common nonmono-tonic technique that allows for dealing with neg-ative information in knowledge and data bases. We present a detailed analysis of the compu-tational 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 tractabil-ity/intractability frontier for such a form of non-monotonic reasoning. We also discuss how to use our results in order to characterize the com-putational complexity of other problems related to nonmonotonic inheritance, diagnosis, and de-fault reasoning. 1