一句话：分类任意置换群上的最小操作，并证明缺少二元本质 polymorphism 可致非刚性结构 CSP NP-hard。
本文研究有限及 omega-categorical 设定下非刚性结构的约束满足问题（CSP）。作者证明，对于（模型完全的）核，若其自同构群不是 Boolean 群的自由作用，则不存在二元本质 polymorphism 可作为 CSP NP-hard 的充分条件。为理解低元数 polymorphism 的行为，作者分类了任意置换群之上的最小操作类型，推广了 Rosenberg 关于平凡群的经典定理，并显著改进了 Bodirsky 与 Chen 关于 omega-categorical 结构自同构群的结果。最后回答 Bodirsky 关于无穷模板二元 polymorphism 的三个问题。
We study constraint satisfaction problems of non-rigid structures in a finite and omega-categorical setting. We show that not having a binary essential polymorphism is a sufficient criterion for NP-hardness of the constraint satisfaction problem of a (model-complete) core, as long as its automorphism group is not the free action of a Boolean group. To understand the behaviour of low arity polymorphisms, we classify the possible types of minimal operations above an arbitrary permutation group. In this, we generalise a classical theorem of Rosenberg above the trivial group, and significantly improve a result of Bodirsky and Chen above the automorphism groups of omega-categorical structures. Finally, we answer three questions of Bodirsky on binary polymorphisms of infinite templates for constraint satisfaction problems.
DOI 原文 ·
@inproceedings{paperbot8631,
title = {Binary symmetries of tractable non-rigid structures},
author = {Paolo Marimon and Michael Pinsker},
booktitle = {LICS},
year = {2025},
doi = {10.1109/lics65433.2025.00036}
}