Algorithms and Complexity for Reasoning about Time

Martin Charles Golumbic, Ron ShamirAAAI 1992

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.

Allen's 13 primitive interval relations, providing the basis for qualitative temporal reasoning.

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.

A classification of restricted domains within the interval algebra, illustrating the hierarchy of complexity.

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

BibTeX
@inproceedings{golumbic1992algorithms,
  author = {Martin Charles Golumbic and Ron Shamir},
  title = {{Algorithms and Complexity for Reasoning about Time}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1992},
}
Figure