一句话：证明无限域 CSP 二分猜想中高度 1 恒等式的局部与全局满足不同，拓扑不可忽略。
论文研究有限有界齐次结构归约的无限域约束满足问题（CSP）的代数二分猜想。该猜想认为，当模板的 model-complete core 具有 pseudo-Siggers 多态时 CSP 多项式时间可解，否则 NP 完全。核心问题是：能否像有限结构情形那样，用固定高度 1 恒等式（不含嵌套函数符号）替代 pseudo-Siggers 多态条件。作者给出否定回答：对每个非平凡高度 1 恒等式集合，构造一个结构，其多态不满足这些恒等式，但 CSP 仍然 tractable。等价地，二分猜想也可通过多态局部满足非平凡高度 1 恒等式来刻画 tractability。作者进一步证明，对轨道增长低于双指数的 ω-范畴结构，局部满足与全局满足非平凡高度 1 恒等式并不相同，从而解决了该代数理论中的一个主要公开问题，说明拓扑在其中确实相关。
The algebraic dichotomy conjecture for Constraint Satisfaction Problems (CSPs) of reducts of (infinite) finitely bounded homogeneous structures states that such CSPs are polynomial-time tractable when the model-complete core of the template has a pseudo-Siggers polymorphism, and NP-complete otherwise. One of the important questions related to this conjecture is whether, similarly to the case of finite structures, the condition of having a pseudo-Siggers polymorphism can be replaced by the condition of having polymorphisms satisfying a fixed set of identities of height 1, i.e., identities which do not contain any nesting of functional symbols. We provide a negative answer to this question by constructing for each non-trivial set of height 1 identities a structure whose polymorphisms do not satisfy these identities, but whose CSP is tractable nevertheless. An equivalent formulation of the dichotomy conjecture characterizes tractability of the CSP via the local satisfaction of nontrivial height 1 identities by polymorphisms of the structure. We show that local satisfaction and global satisfaction of nontrivial height 1 identities differ for ω -categorical structures with less than double exponential orbit growth, thereby resolving one of the main open problems in the algebraic theory of such structures.
@inproceedings{paperbot4999,
title = {Topology is relevant (in a dichotomy conjecture for infinite-domain constraint satisfaction problems)},
author = {Manuel Bodirsky and Antoine Mottet and Miroslav Olsak and Jakub Oprsal and Michael Pinsker and Ross Willard},
booktitle = {LICS},
year = {2019},
doi = {10.1109/lics.2019.8785883}
}