一句话：证明了一元结构一阶归约的 CSP 二分性，并给出无限域 CSP 到有限域 CSP 的多项式时间归约与可解性条件。
论文研究有限有界齐次结构归约上的约束满足问题（CSP），该类比有限域 CSP 更广。作者首先给出从这类无限域 CSP 到有限域 CSP 的一般多项式时间归约，并据此得到可用拓扑多态克隆表达的若干强多项式时间可解性条件。随后聚焦于一元语言结构的归约类 C，证明它严格包含所有有限域 CSP。利用上述可解性条件，作者证明了 Bodirsky 与 Pinsker 关于有限有界齐次结构归约的一般可解性猜想在类 C 上成立，从而给出该类 CSP 的二分结果。
Many natural decision problems can be formulated as constraint satisfaction problems for reducts $\mathbb{A}$ of finitely bounded homogeneous structures. This class of problems is a large generalisation of the class of CSPs over finite domains. Our first result is a general polynomial-time reduction from such infinite-domain CSPs to finite-domain CSPs. We use this reduction to obtain new powerful polynomial-time tractability conditions that can be expressed in terms of the topological polymorphism clone of $\mathbb{A}$. Moreover, we study the subclass $\mathcal{C}$ of CSPs for structures $\mathbb{A}$ that are reducts of a structure with a unary language. Also this class $\mathcal{C}$ properly extends the class of all finite-domain CSPs. We apply our new tractability conditions to prove the general tractability conjecture of Bodirsky and Pinsker for reducts of finitely bounded homogeneous structures for the class $\mathcal{C}$.
@article{paperbot404,
title = {A Dichotomy for First-Order Reducts of Unary Structures},
author = {Manuel Bodirsky and Antoine Mottet},
journal = {Logical Methods in Computer Science},
volume = {Volume 14, Issue 2},
year = {2018},
doi = {10.23638/lmcs-14(2:13)2018}
}