Closing Computational Complexity Gaps in Logic

This direction is split into other directions: computational complexity gap. Its last version stays readable and citable here.

Version 1 of 1183 papers205 conceptsfrozen 2026-10-04

In the field of formal logic and knowledge representation, proving that a problem is "decidable" is only the first step. For engineers building query engines or verification tools, the real question is: How hard is it, exactly?

A recurring theme across recent research is the effort to close "complexity gaps"—the theoretical space between a known lower bound (the minimum difficulty we’ve proven) and an upper bound (the efficiency of our best current algorithm). When these bounds don't match, we don't truly understand the problem's inherent difficulty. Researchers like Carsten Lutz, Frank Wolter, and Meghyn Bienvenu are systematically narrowing these gaps to provide the "tight" bounds necessary for optimal system design.

The Anatomy of a Complexity Gap

Imagine you are designing a system to check if one database query is "contained" within another. If a researcher proves the problem is PSPACE-hard, they are saying, "It is at least as difficult as any problem in PSPACE." If another researcher provides an algorithm that runs in 2-EXPTIME, they are saying, "We can definitely solve it within this much time."

The "gap" is the uncertainty in between. Is the problem actually PSPACE-complete, meaning our 2-EXPTIME algorithm is wildly inefficient? Or is it 2-EXPTIME-complete, meaning the problem is fundamentally much harder than we initially thought?

For example, in Containment for Rule-Based Ontology-Mediated Queries, Pablo Barcelo and Andreas Pieris note that while they have established sharp bounds for many rule families, a gap remains for non-recursive existential rules, currently floating between PNEXP and ExpSpace.

Why Gaps Persist: The Cost of Expressivity

Gaps often appear when we add "expressive" features to a logic—features that make it more useful for real-world data but harder to analyze.

  1. Inverse Roles: In Description Logics (DLs), being able to look at a relationship "backwards" (e.g., if X "is parent of" Y, then Y "is child of" X) is crucial. However, Carsten Lutz demonstrated in Inverse Roles Make Conjunctive Queries Hard that this feature can cause a double-exponential jump in complexity, resolving a long-standing uncertainty about whether more efficient methods were possible.
  2. Transitivity: Relationships like "part-of" are transitive. In Query Answering in Description Logics with Transitive Roles, evidence shows that combining transitivity with role hierarchies creates a gap where the problem is known to be at least CO-NEXPTIME-hard, but potentially as difficult as 2-EXPTIME.
  3. Counting and Arithmetic: When we ask "how many" (cardinality queries), the complexity can shift unpredictably. Meghyn Bienvenu and Michaël Thomazo show in Cardinality Queries over DL-Lite Ontologies that while some counting is easy ($TC^0$), adding role hierarchies can push the problem into coNP-completeness.

Closing the Gap: Tightening the Bounds

Closing a gap usually requires one of two breakthroughs: a more clever algorithm (lowering the upper bound) or a more sophisticated mathematical reduction (raising the lower bound).

In Containment in Monadic Disjunctive Datalog, MMSNP, and Expressive Description Logics, Pierre Bourhis successfully closed a major gap by proving that query containment for these formalisms is 2NEXPTIME-complete. This "tight" result tells us exactly where the ceiling is: the complexity is driven by the size of the query, not the ontology itself.

Similarly, Stefan Göller and Stefan Kiefer tackled the problem of behavioral equivalence in recursive programs. In Bisimilarity of Pushdown Systems is Nonelementary, they proved the lower bound is "nonelementary"—meaning it grows faster than any tower of exponentials. While a matching upper bound is still being sought, this result drastically shifted the field's understanding of the problem's scale.

The Intuition of "Completeness"

When a researcher proves a problem is Complete for a complexity class (like 2-EXPTIME-complete), they have effectively "closed the gap." Completeness is the holy grail because it proves that:

  • Upper Bound: We have an algorithm to solve it.
  • Lower Bound: Any other problem in that class can be translated into this one.

Without completeness, as noted by Arne Meier and Michael Thomas 0001 in The complexity of propositional implication, we are often left with "membership" results that don't tell us if a more efficient solution exists. Proving completeness often requires solving deep questions about the relationships between different types of computational circuits or automata.

Why It Matters

These theoretical gaps have practical consequences. If we don't know the exact complexity of a logic, we don't know if our search algorithms are optimal. As Sarath Sreedharan and Subbarao Kambhampati argue in On the Computational Complexity of Model Reconciliations, the absence of formal complexity classifications prevents researchers from knowing if their specialized AI planning explanations are as efficient as they can possibly be. By closing these gaps, the research community provides the blueprints for the next generation of high-performance, verified reasoning tools.

Papers in this version

Showing 60 of 183 papers.

History & citationVersion 1 · 2026-10-04

Split into other directions · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_closing_computational_complexity_gaps_in_82f6497b,
  title = {Closing Computational Complexity Gaps in Logic},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/closing-computational-complexity-gaps-in-logic/rdr_82f6497bd4334c18af4535db489852d5},
  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_closing_computational_complexity_gaps_in_82f6497b_v1,
  title = {Closing Computational Complexity Gaps in Logic},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/closing-computational-complexity-gaps-in-logic/rdr_82f6497bd4334c18af4535db489852d5/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-22},
}