The Complexity of Non-Monotonic Reasoning in Description Logics

You are reading version 1 of this direction, frozen 2026-10-04. The latest version is version 2.

Version 1 of 2168 papers231 conceptsfrozen 2026-10-04

In classical logic, knowledge is monotonic: once you prove a statement true, it remains true regardless of what new information you acquire. However, human "common sense" is inherently non-monotonic. We assume birds fly until we encounter a penguin, at which point we revise our belief.

To bridge this gap, researchers have integrated non-monotonic mechanisms like circumscription, default logic, and aggregates into Description Logics (DLs)—the formal languages powering the Semantic Web. While these features allow for more realistic modeling, they come with a "complexity tax" that often pushes reasoning from efficient polynomial time into the upper reaches of the complexity hierarchy.

The Mechanism of Minimization

The most prominent way to handle exceptions in formal ontologies is through circumscription. As explored by Christos Papadimitriou and Phokion G. Kolaitis in Some Computational Aspects of Circumscription, circumscription works by minimizing the extension of certain predicates.

Imagine a "bird" ontology. In standard logic, if you don't know whether a specific bird flies, the system remains undecided. Under circumscription, you minimize the "abnormal" predicate. You essentially tell the system: "Assume everything is normal unless proven otherwise." If the system cannot prove a bird is a penguin or injured, it concludes the bird flies.

However, this "minimization" is computationally expensive. Jonathan Stillman showed in The Complexity of Propositional Default Logics that this requires nested consistency checks. To apply a default rule, the system must verify that the conclusion is consistent with everything else it knows—effectively requiring an "NP-oracle" call within an already non-deterministic process. This places even simple default reasoning at the second level of the polynomial hierarchy ($\Sigma^P_2$ or $\Pi^P_2$).

The Complexity Rollercoaster

When these non-monotonic tools are added to expressive logics, the results are often dramatic. Quentin Manière describes this as a "complexity rollercoaster" in Adding Circumscription to Decidable Fragments of First-Order Logic.

For example, the Guarded Fragment (GF) of first-order logic is typically well-behaved. But adding circumscription causes a massive explosion, jumping from doubly-exponential complexity to TOWER-complete. Similarly, Carsten Lutz and Frank Wolter demonstrated in The Complexity of Circumscription in DLs that integrating circumscription into standard Description Logics increases complexity to NExpTime-complete or even NExp$^{NP}$-complete.

This jump occurs because non-monotonicity breaks the "tree model property" that many efficient logics rely on. In a standard DL, you can reason about an individual by looking at its immediate neighbors. In a circumscribed DL, the truth of a statement might depend on the global minimization of a predicate across the entire model, forcing the reasoner to consider the state of the whole world at once.

Finding the Tractability Frontier

Given these high costs, a major research direction involves finding the "tractability frontier"—the exact point where we can have non-monotonicity without losing efficiency.

  1. Lightweight Logics: Piero A. Bonatti and colleagues explored adding "defeasible inheritance" to the $\mathcal{EL}^{++}$ logic, which is used for massive medical ontologies like SNOMED CT. In Adding Default Attributes to EL++, they identified a "Strong Conflict Safety" condition. If the ontology avoids certain types of circular conflicts between defaults, reasoning can stay in polynomial time.
  2. Data Complexity: Even if the overall reasoning is hard, query answering might still be feasible if the "hard part" depends on the size of the schema (which is small) rather than the size of the data (which is large). Robin Nolte and Quentin Manière showed in Querying Circumscribed Description Logic Knowledge Bases that for certain logic families, data complexity remains manageable at $\Pi^P_2$-completeness, even when the general problem is much harder.

Hybrid Systems and Aggregates

The challenge extends to hybrid systems that combine ontologies with rules (Logic Programming). Xiaoping Chen introduced $\mathcal{DL}log$ in DL_clog: A Hybrid System Integrating Rules and Description Logics with Circumscription, which allows rules to reason about what is not known in an ontology. This integration is powerful for the Semantic Web but results in a satisfiability problem that is NExp$^{NP}$-complete.

A similar pattern appears in Answer Set Programming (ASP) when dealing with aggregates (like counts or averages). Francesco Calimeri and Nicola Leone proved in Declarative and Computational Properties of Logic Programs with Aggregates that while monotone aggregates (like COUNT > 5) are relatively easy, non-monotone aggregates (like AVERAGE = 10) shift the complexity to the second level of the polynomial hierarchy.

Summary of the Trade-off

The research across these 122 papers converges on a single reality: the cost of common sense is high. * Monotonic Logic: Efficient, local, but rigid (cannot handle exceptions). * Non-Monotonic Logic: Flexible, global, but computationally demanding (often NP-hard or exponential).

The field continues to map this landscape, seeking specific structural constraints—like those found in Query Answering for Rough EL Ontologies by Anni-Yasmin Turhan—that allow us to model the messy, exception-filled real world without building systems that are too slow to use.

Papers in this version

Showing 60 of 168 papers.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 144 papers
  2. Version 1 · 2026-10-04 · 168 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_computational_complexity_of_nonmonotonic_33dcfa3f,
  title = {computational complexity of nonmonotonic reasoning},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/computational-complexity-of-nonmonotonic-reasoning/rdr_33dcfa3f231548c5b8814613c719de54},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_the_complexity_of_non_monotonic_reasonin_33dcfa3f_v1,
  title = {The Complexity of Non-Monotonic Reasoning in Description Logics},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/the-complexity-of-non-monotonic-reasoning-in-description-logics/rdr_33dcfa3f231548c5b8814613c719de54/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}