论文标题
通过拉姆齐理论的空间推理中的复杂性二分法
A Complexity Dichotomy in Spatial Reasoning via Ramsey Theory
论文作者
论文摘要
有限界均匀结构的一阶还原的一阶还原的约束满意度问题构成了一类可能表现出复杂性二分法的计算问题，P与NP完整性相比。获得此类CSP的多项式障碍结果的一种强大方法是，对于足够大的k，在K-types上定义的多项式可拖动有限域CSP的一定降低。当可以应用这种方法并说明如何使用一般结果证明新的复杂性二分法，以进行良好的空间推理形式主义RCC5的基本关系的一阶扩展，我们会提供足够的条件。我们还对这些CSP中的哪些可以在DataLog中进行分类。我们的方法依赖于拉姆齐理论。我们证明RCC5具有Ramsey订单的扩展。
Constraint satisfaction problems (CSPs) for first-order reducts of finitely bounded homogeneous structures form a large class of computational problems that might exhibit a complexity dichotomy, P versus NP-complete. A powerful method to obtain polynomial-time tractability results for such CSPs is a certain reduction to polynomial-time tractable finite-domain CSPs defined over k-types, for a sufficiently large k. We give sufficient conditions when this method can be applied and illustrate how to use the general results to prove a new complexity dichotomy for first-order expansions of the basic relations of the well-studied spatial reasoning formalism RCC5. We also classify which of these CSPs can be expressed in Datalog. Our method relies on Ramsey theory; we prove that RCC5 has a Ramsey order expansion.
