# Improved Algorithms for Allen's Interval Algebra by Dynamic Programming with Sublinear Partitioning

arXiv: https://arxiv.org/abs/2305.15950 · HTML: https://mlsanity.com/paper/2305.15950/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Placed in Mathematical reasoning, one of 17 directions in LLM reasoning.
- Builds on 1 of its 19 references that are in the map.
- First posted on arXiv 25 May 2023.

## Placed in

- LLM reasoning / [Mathematical reasoning](https://mlsanity.com/lr/mathematical-reasoning/)

## Builds on (most cited first, 1 of 1)

- [A Multivariate Complexity Analysis of Qualitative Reasoning Problems](https://mlsanity.com/paper/2209.15275/) (2022)

## Built on by (most cited first, 1 of 1)

- [Maximum Satisfiability of Simple Temporal Problems](https://mlsanity.com/paper/2607.23785/) (2026)

## Abstract (arXiv)

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.