A Multivariate Complexity Analysis of Qualitative Reasoning Problems
This work addresses a fundamental bottleneck in AI for researchers and practitioners in qualitative reasoning, offering a novel approach to improve algorithm efficiency, though it is incremental in advancing existing complexity classes.
The paper tackles the challenge of achieving single-exponential time algorithms for qualitative reasoning problems, such as Allen's interval algebra, by introducing a multivariate complexity analysis with parameters n and k, and demonstrates results like solving the Partially Ordered Time problem in 16^{kn} time and the network consistency problem in (2nk)^{2k} * 2^n time.
Qualitative reasoning is an important subfield of artificial intelligence where one describes relationships with qualitative, rather than numerical, relations. Many such reasoning tasks, e.g., Allen's interval algebra, can be solved in $2^{O(n \cdot \log n)}$ time, but single-exponential running times $2^{O(n)}$ are currently far out of reach. In this paper we consider single-exponential algorithms via a multivariate analysis consisting of a fine-grained parameter $n$ (e.g., the number of variables) and a coarse-grained parameter $k$ expected to be relatively small. We introduce the classes FPE and XE of problems solvable in $f(k) \cdot 2^{O(n)}$, respectively $f(k)^n$, time, and prove several fundamental properties of these classes. We proceed by studying temporal reasoning problems and (1) show that the Partially Ordered Time problem of effective width $k$ is solvable in $16^{kn}$ time and is thus included in XE, and (2) that the network consistency problem for Allen's interval algebra with no interval overlapping with more than $k$ others is solvable in $(2nk)^{2k} \cdot 2^{n}$ time and is included in FPE. Our multivariate approach is in no way limited to these to specific problems and may be a generally useful approach for obtaining single-exponential algorithms.