Closing Complexity Gaps in Description Logics

26 concepts26 papers1 proposal

When computer scientists analyze a logic or a query language, their ultimate goal is to pin down its exact computational difficulty. This requires establishing two boundaries: an upper bound (by designing an algorithm that solves the problem within a certain amount of time or space) and a lower bound (by proving that the problem is mathematically impossible to solve any faster).

Ideally, these two bounds meet, yielding a "tight" complexity classification. However, in many expressive logics, a significant complexity gap persists. For example, we might possess an algorithm that solves a problem in double-exponential time ($\text{2EXPTIME}$), yet our best lower bound only proves the problem is $\text{PSPACE}$-hard.

A complexity gap represents a profound piece of missing knowledge. It means either our current algorithms are unnecessarily slow and a breakthrough optimization is waiting to be discovered, or the problem is fundamentally harder than we have been able to prove, meaning our theoretical understanding of its worst-case behavior is incomplete. The research direction outlined here focuses on systematically closing these gaps across description logics, modal logics, and query languages.


Where the Gaps Hide: Queries and Ontologies

Complexity gaps frequently emerge when we combine structured knowledge bases (ontologies) with expressive query languages. Every time a new feature is added to a logic—such as inverse roles, counting constraints, or recursion—it alters how information propagates through the underlying models, often leaving theoretical analysis lagging behind.

Consider the task of answering regular path queries over description logics. Diego Calvanese et al. demonstrated in Answering Regular Path Queries in Expressive Description Logics: An Automata-Theoretic Approach that an upper bound of $\text{2EXPTIME}$ could be achieved. However, a wide gap remained from the known exponential space lower bound when certain features like inverse roles were omitted. Similarly, when dealing with transitive roles, Thomas Eiter et al. noted in Query Answering in Description Logics with Transitive Roles that the exact classification was unresolved, spanning a gap from a $\text{co-NEXPTIME}$-hard lower bound up to a $\text{2EXPTIME}$ upper bound.

Gaps are not limited to query answering; they also plague static analysis tasks, such as determining if two ontologies are functionally identical. In Conjunctive Query Inseparability of OWL 2 QL TBoxes, Boris Konev et al. highlighted an unresolved gap between a $\text{PSPACE}$-hard lower bound and an $\text{EXPTIME}$ upper bound for deciding query inseparability. This uncertainty prevents developers from knowing whether it is possible to build significantly faster tools to compare or optimize large-scale ontologies.


Why Are These Gaps So Hard to Close?

To close a gap, researchers must either find a more efficient algorithm (lowering the upper bound) or construct a more clever reduction to prove a harder worst-case scenario (raising the lower bound). The difficulty lies in the subtle, often invisible interactions between logical operators.

For instance, adding counting capabilities or cardinality constraints completely changes how data scales. As explored by Meghyn Bienvenu et al. in Cardinality Queries over DL-Lite Ontologies, combining role hierarchies with negative constraints introduces unresolved data complexity bounds. We know the problem sits somewhere between highly efficient parallel classes like $\text{TC}^0$ and harder classes like $\text{coNP}$, but pinpointing the exact boundary requires untangling how constraints force data values to merge.

Sometimes, a gap persists because it is unclear whether an explosion in complexity is an inherent property of the logic itself or merely an artifact of how we encode our algorithms. Ian Horrocks et al. encountered this in Deciding SHOQ^cap Knowledge Base Consistency using Alternating Automata, where introducing role conjunctions caused a jump to double-exponential time, leaving it an open question whether a single-exponential approach was theoretically possible or fundamentally barred by the logic's expressivity.


Strategies for Tightening the Bounds

To bridge these chasms, researchers employ several sophisticated mathematical and algorithmic frameworks:

  • Automata-Theoretic Reductions: By translating logical formulas into tree automata, researchers can transform semantic consistency checks into structural emptiness problems. This approach allows them to map out the exact state-space explosion and establish clean upper bounds.
  • Consequence-Based Reasoning: Traditional tableau methods can be slow because they explore many redundant paths. Consequence-based algorithms, such as those analyzed by David Jaime Tena Cucala et al. in Consequence-based Reasoning for Description Logics with Disjunction, Inverse Roles, Number Restrictions, and Nominals, attempt to close the gap between practical algorithmic performance and theoretical lower bounds by deriving direct implications in a goal-oriented manner.
  • Compilability Boundaries: Another way to understand a logic's true cost is to see if it can be compiled into a simpler language without exponential growth. For example, Stefan Borgwardt et al. in Expressivity of Planning with Horn Description Logic Ontologies mapped the boundaries of compiling Horn Description Logics into standard planning languages, identifying exactly where efficient transformations are possible and where exponential blowups are unavoidable.

Ultimately, resolving these computational complexity gaps is about drawing the exact borders of tractability. By systematically squeezing the space between lower and upper bounds, the community moves from heuristic-driven engineering to provably optimal reasoning engines.

Key Foundational Work

On the Universal and Existential Fragments of the µ-Calculus (2003) — contributed 1 concept elements to this direction.
Fusions of Description Logics and Abstract Description Systems (2002) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

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

This exact version (version 1, frozen text):

@misc{lacuna_computational_complexity_gap_46ebf2cb_v1,
  title = {computational complexity gap},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/computational-complexity-gap/rdr_46ebf2cb7c844d829e8515e14d2517df/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-22},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake