Is Intractability of Non-Monotonic Reasoning a Real Drawback?

Marco Cadoli, Francesco M. Donini, Marco Schaerf

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.


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.