Is Intractability of Non-Monotonic Reasoning a Real Drawback?

Nonmonotonic Reasoning

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 12

Nonmonotonic Reasoning

Several studies about complexity of NMR showed that inferring in non-monotonic knowledge bases is significantly harder than reasoning in monotonic ones. This contrasts with the general idea that NMR can be used to make knowledge representation and reasoning simpler, not harder. In this paper we show that, to some extent, NMR has fulfilled its goal. In particular we prove that circumscription allows for more compact and natural representation of knowledge. Results about intractability of circumscription can therefore be interpreted as the price one has to pay for having such an extra-compact representation. On the other hand, sometimes NMR really makes reasoning simpler; we give prototypical scenarios where closed-worId reasoning accounts for a faster and unsound approximation of classical reasoning.