一句话：给出将这类无限域 CSP 归约到 k-型有限域 CSP 的充分条件，并用于证明 RCC5 一阶扩展的新复杂度二分。
本文研究有限有界齐次结构的一阶归约上的约束满足问题（CSP）。这类无限域 CSP 被认为可能展现 P 与 NP-完全的复杂度二分。已有强有力方法可将其归约到定义在 k-型上的有限域 CSP，从而借助有限域多态获得多项式时间可解结果。作者给出该方法可应用的充分条件，核心涉及 Ramsey 结构、典范多态（canonical polymorphisms）以及唯一插值性质。作为应用，他们利用一般性结果证明了空间推理形式化 RCC5 的基本关系的一阶扩展的新复杂度二分。工作为无限域 CSP 的可解性归约提供了模型论工具，并扩展了已知二分结果的范围。
Constraint satisfaction problems 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 de-fined 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 spatial reasoning formalism RCC5.
DOI 原文 ·
@inproceedings{paperbot6210,
title = {Canonical Polymorphisms of Ramsey Structures and the Unique Interpolation Property},
author = {Manuel Bodirsky and Bertalan Bodor},
booktitle = {LICS},
year = {2021},
doi = {10.1109/lics52264.2021.9470683}
}