Is Intractability of Non-Monotonic Reasoning a Real Drawback?

Marco Cadoli, Francesco M. Donini, Marco SchaerfAAAI 1994

Introduction

In the early 1990s, the Artificial Intelligence community encountered a significant theoretical hurdle. Non-Monotonic Reasoning (NMR)—a logical framework where new information can invalidate previous conclusions—was developed to mirror human common-sense reasoning. However, computational complexity analysis revealed that NMR was often significantly more expensive than classical monotonic reasoning. For instance, inference in Horn formula fragments is linear in classical logic but becomes co-NP-complete under NMR. This paper investigates whether this "intractability" is a fundamental flaw or a necessary consequence of the expressive power NMR provides.

The Paradox of Complexity

The central question is whether the increased computational cost of NMR is justified. If NMR is harder for computers to process, why use it? The authors argue that the perceived slowness is a trade-off for representational compactness. NMR allows for exponentially more compact knowledge bases than classical logic. When comparing the two on the same input size, NMR seems slower; however, the NMR input is often much smaller because it captures implicit information that classical logic would require to be explicitly defined.

Methodology: Circumscription and Compilability

The study focuses on two major NMR formalisms: Circumscription (CIRC) and the Closed-World Assumption (CWA). To analyze these, the authors introduce pedagogical examples like the "Lazy Student" and "Cautious Student" to illustrate how NMR handles preferences and guarantees.

Figure 1: Example logical constraints representing student curriculum preferences, illustrating the use of disjunctions to model choices.

A key technical contribution is the proof of "non-compilability." Using the complexity class of non-uniform P, the authors demonstrate that an NMR knowledge base cannot be "compiled" into a polynomial-sized classical structure that allows for polynomial-time query answering. This suggests that the complexity is inherent to the representation itself.

Key Results and Insights

The authors' findings are summarized in their analysis of 2-CNF and Definite Horn formulas. They prove that for these fragments, NMR queries remain intractable even with extensive pre-processing, unless standard complexity assumptions (like $NP \subseteq \text{non-uniform } P$) are incorrect.

Figure 2: Summary of compilability results for NMR queries, highlighting the conditions under which queries are non-compilable according to Theorems 2 and 4.

Beyond the "drawback" of complexity, the paper highlights a surprising benefit: NMR can act as a "fast and dirty" approximation. In certain scenarios, finding a minimal model (NMR) is in Polynomial time (P), while proving a statement in all classical models is co-NP-complete. Thus, NMR can provide a complete but unsound approximation that is faster than its classical counterpart.

Conclusion

The intractability of Non-Monotonic Reasoning is not a "bug" but a feature of its efficiency in representing complex information. By allowing for massive space savings and providing mechanisms for fast (if unsound) approximations, NMR offers a sophisticated toolset for AI that classical logic cannot match in terms of compactness. Future work will look to extend these propositional results to first-order logic and identify more prototypical scenarios where NMR's strengths are most apparent.

Summary updated

BibTeX
@inproceedings{cadoli1994is,
  author = {Marco Cadoli and Francesco M. Donini and Marco Schaerf},
  title = {{Is Intractability of Non-Monotonic Reasoning a Real Drawback?}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1994},
}
Figure