Introduction
Temporal reasoning is a critical component in diverse fields such as artificial intelligence planning, molecular biology, and archaeology. At its core, it involves managing and inferring relationships between intervals of time or space. For example, given that Event A occurred before Event B, and Event B overlaps with Event C, a reasoning system must determine the possible relationships between A and C.
James Allen’s 13-valued interval algebra ($A_{13}$) is the standard model for such qualitative reasoning. However, the general problem of finding a consistent set of relationships in $A_{13}$ is NP-complete. This paper explores the boundary between tractability and intractability by investigating "macro relations" and restricted domains within this algebra.
Methodology: The Graph Sandwich Problem
The authors employ a combination of complexity theory and graph-theoretic techniques to analyze temporal consistency. A key innovation is the introduction of the Interval Graph Sandwich Problem (IGS). This problem asks whether there exists an interval graph that contains a set of required edges and excludes a set of forbidden edges. By linking temporal reasoning to this graph problem, the authors leverage established graph theory to derive complexity results.
For tractable sub-problems, the research utilizes endpoint modeling. By translating interval relationships into linear inequalities between the start and end points of intervals, the problem can be reduced to finding valid orderings in directed acyclic graphs (DAGs), which can be accomplished in linear time.
Key Insights
A primary insight of the paper is that simplifying the algebra does not automatically guarantee computational efficiency. The authors demonstrate that even the 3-valued algebra ($A_3$)—which only considers precedence, subsequence, and intersection—is NP-complete. This suggests that the fundamental difficulty of temporal reasoning is rooted in basic concepts like "before" and "intersecting."
However, the "disjoint" relation is identified as a key driver of complexity. When this relation is excluded or appropriately restricted, the problem often becomes solvable in linear time through endpoint ordering. Furthermore, the authors prove that for these algebras, the decision problem (satisfiability) is polynomially equivalent to the labeling problem (identifying all consistent relations).
Results and Classification
The paper provides a detailed mapping of the complexity of restricted domains. Of the 31 possible restricted domains within the $A_3$ algebra, the authors successfully classified 27.
Key results include:
- NP-Completeness Proofs: Formal proof that the IGS problem and Interval Satisfiability (ISAT) for the $A_3$ algebra are NP-complete.
- Linear-Time Algorithms: Development of a linear-time algorithm for specific domains, such as $A_3$ without the "disjoint" relation.
- Polynomial-Time Solutions: An $O(n^3)$ algorithm for domains involving precedence and intersection, utilizing chordal graph recognition.
Conclusion
This research clarifies the computational landscape of qualitative temporal reasoning. While identifying several tractable fragments, it also highlights the inherent difficulty of even simplified interval algebras. Future work remains to classify the four remaining cases in $A_3$ and to extend these qualitative results to include quantitative constraints, such as specific durations or time offsets.
Summary updated