2023/05/25 by Leif A. Eriksson, Victor Lagerkvist, Eriksson, Leif +1 · 1 citation
Computer Science · #AI-based Problem Solving and Planning #Artificial Intelligence (cs.AI) #Computational Complexity (cs.CC) #Constraint Satisfaction and Optimization #FOS: Computer and information sciences #Logic, Reasoning, and Knowledge
paper · pdf · doi:10.48550/arxiv.2305.15950
openalex publication_date 2023/05/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
Allen's interval algebra is one of the most well-known calculi in qualitative temporal reasoning with numerous applications in artificial intelligence. Recently, there has been a surge of improvements in the fine-grained complexity of NP-hard reasoning tasks, improving the running time from the naive 2O(n2) to O^*((1.0615n)n), with even faster algorithms for unit intervals a bounded number of overlapping intervals (the O^*(⋅) notation suppresses polynomial factors). Despite these improvements the best known lower bound is still only 2o(n) (under the exponential-time hypothesis) and major improvements in either direction seemingly require fundamental advances in computational complexity. In this paper we propose a novel framework for solving NP-hard qualitative reasoning problems which we refer to as dynamic programming with sublinear partitioning. Using this technique we obtain a major improvement of O^*((\fraccnlogn)n) for Allen's interval algebra. To demonstrate that the technique is applicable to more domains we apply it to a problem in qualitative spatial reasoning, the cardinal direction point algebra, and solve it in O^*((\fraccnlogn)2n/3) time. Hence, not only do we significantly advance the state-of-the-art for NP-hard qualitative reasoning problems, but obtain a novel algorithmic technique that is likely applicable to many problems where 2O(n) time algorithms are unlikely.