Local-to-Global Consistency Implies Tractability of Abduction

Michal WronaAAAI 2014 · DOI

Introduction

Abduction is a fundamental reasoning process in artificial intelligence, often described as the "logic of discovery." It involves identifying a set of hypotheses ($H$) that, when combined with a background knowledge base ($KB$), logically entail an observed manifestation ($M$). While conceptually straightforward, abduction is computationally demanding. In many settings, it resides in the $\Sigma^P_2$ complexity class—making it significantly harder than standard NP-complete search problems.

This paper addresses the challenge of finding "islands of tractability" within abductive reasoning. The authors demonstrate that a specific structural property—local-to-global consistency—serves as a sufficient condition to reduce the complexity of abduction from $\Sigma^P_2$ to polynomial time (P).

The Complexity of Abduction

In the context of Constraint Satisfaction Problems (CSPs), abduction requires finding a consistent set of constraints that force a specific outcome. The difficulty arises because one must not only find a solution but ensure that all models of the combined $KB$ and $H$ satisfy $M$.

The authors focus on abduction within infinite-domain structures that are $\omega$-categorical. These structures, such as the rational numbers under the standard ordering, allow for the representation of infinite relations through finite symmetries. By focusing on "Orbit Abduction" (OE-ABD), where hypotheses are restricted to the orbits of the structure’s automorphism group, the researchers provide a framework that is both expressive and mathematically manageable.

Local-to-Global Consistency and $k$-Decomposability

The core insight of the paper is the application of local-to-global consistency. A constraint language $\Gamma$ possesses this property if establishing consistency among small subsets of variables (local consistency) is sufficient to guarantee the existence of a global solution.

The authors link this to the concept of $(k-1)$-decomposability. If a language is $(k-1)$-decomposable, the set of all solutions can be represented by looking at constraints on subsets of size $k$. This structural simplification allows the complex logical requirements of abduction to collapse into a series of local, polynomial-time checks.

The LtG-OEAbd Algorithm

The paper introduces the LtG-OEAbd algorithm, which leverages these structural properties to solve Orbit Abduction efficiently. The algorithm operates through two primary mechanisms:

  1. Decomposition: It computes a $(k+1)$-decomposition of the knowledge base, representing the solution space through local constraints.
  2. Zanuttini’s Condition: The algorithm adapts a condition originally developed for propositional logic. It compares the partial assignments consistent with the $KB$ against those consistent with the $KB$ plus the manifestation. If a partial assignment exists that is consistent with the $KB$ but cannot be extended to satisfy the manifestation, the algorithm identifies the necessary explanation.

By "lifting" Zanuttini’s condition from simple Boolean logic to infinite relational structures, the authors provide a powerful tool for qualitative reasoning.

Applications in Temporal and Spatial Reasoning

The theoretical results are validated across several well-known frameworks in AI:

  • Temporal Reasoning: The algorithm provides a polynomial-time solution for abduction in Point Algebra (e.g., $x < y$) and Allen’s Interval Algebra (e.g., "overlaps," "during"). Specifically, it covers the "basic Ord-Horn" fragments essential for temporal databases.
  • Spatial Reasoning: The paper proves tractability for fragments of RCC-5 (Region Connection Calculus), a standard for geographic information systems (GIS).
  • Equality Constraints: It handles basic reasoning regarding variable equality and inequality.

Previously, tractability results for these domains were often treated as isolated cases. This work provides a unified theoretical umbrella that explains why these specific fragments are solvable.

Conclusion and Future Directions

The paper establishes a clear complexity boundary: when local-to-global consistency is present, abduction is tractable; without it, the problem typically reverts to being NP-hard or worse. While the requirement for $\omega$-categorical and homogeneous structures limits the scope to qualitative calculi, the results represent a significant step forward in understanding the limits of efficient reasoning.

Future research may explore even broader conditions, such as "datalog-expressibility," to identify further tractable classes of abduction, potentially expanding the reach of these efficient algorithms to even more complex real-world scenarios.

Summary updated

BibTeX
@inproceedings{wrona2014local,
  author = {Michal Wrona},
  title = {{Local-to-Global Consistency Implies Tractability of Abduction}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2014},
  doi = {10.1609/aaai.v28i1.8861},
}
Figure