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.

本文介绍了单指数算法，并通过多元分析研究了时间推理问题，特别是针对 Allen 的时间间隔代数，证明了一个新问题可以在单指数时间内解决，并且这种方法可以更广泛地用于其他问题。

定性推理问题的多元复杂度分析

A Multivariate Complexity Analysis of Qualitative Reasoning Problems

We study the program complexity of datalog on both finite and infinite linear
orders. Our main result states that on all linear orders with at least two
elements, the nonemptiness problem for datalog is EXPTIME-complete. While
containment of the nonemptiness problem in EXPTIME is known for finite linear
orders and actually for arbitrary finite structures, it is not obvious for
infinite linear orders. It sharply contrasts the situation on other infinite
structures; for example, the datalog nonemptiness problem on an infinite
successor structure is undecidable. We extend our upper bound results to
infinite linear orders with constants.
As an application, we show that the datalog nonemptiness problem on Allen's
interval algebra is EXPTIME-complete.

研究了 datalog 在有限和无限线性序列上的程序复杂性。 结果证明，在具有至少两个元素的所有线性序列上，datalog 的非空问题是 EXPTIME 完全的，将该结果扩展到具有常量的无限线性序列上，并在 Allen 的区间代数上应用这个结果。