论文标题
定性推理问题的多元复杂性分析
A Multivariate Complexity Analysis of Qualitative Reasoning Problems
论文作者
论文摘要
定性推理是人工智能的重要子领域，其中人们描述了与定性的，而不是数字关系的关系。许多这样的推理任务，例如，艾伦的间隔代数，可以以$ 2^{o（n \ cdot \ log n）} $ time求解，但是单个指数运行时间$ 2^{o（n）} $当前远远超出了范围。在本文中，我们通过多变量分析来考虑单指数算法，该算法由细粒的参数$ n $（例如变量数）和预期相对较小的粗粒参数$ k $组成。我们在$ f（k）\ cdot 2^{o（n）} $中介绍了可以解决的问题的类和XE，分别是$ f（k）^n $，时间，并证明了这些类的几个基本属性。我们通过研究时间推理问题进行进行，并且（1）表明，有效宽度$ k $的部分订购时间问题可在$ 16^{kn} $中解决，因此包括在XE中，并且（2）（2）艾伦间隔代数的网络一致性问题无需$ k $ by $ k $ nime nime cdnk $（2nk）cdnk $（2nk）^nk^nk）{2nk）{2nk）{2nk）并包含在FPE中。我们的多元方法绝不限于这些特定问题，并且可能是获得单个指数算法的通常有用的方法。
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.
