一句话：通过本原正可定义性定理与最小 Taylor 代数，统一并简化 CSP 三种代数方法，为二分定理提供新框架。
本文关注约束满足问题（CSP）复杂度与算法背后的代数理论，旨在统一、简化并扩展有限模板 CSP 的三种代数方法：吸收理论、Bulatov 理论与 Zhuk 理论。第一项贡献是给出关于本原正可定义性的初等定理，并将 Bulatov 和 Zhuk 证明的起点作为其推论导出。第二项贡献是提出并初步系统研究最小 Taylor 代数。该代数类足够广泛，只需在其上验证 CSP 二分定理，同时又具有异常良好的性质：三种方法中的许多概念在此类中重合。作者认为该理论有望导向更简单自然的二分定理证明与更高效算法，并帮助解决其他 CSP 相关复杂度问题。
This paper focuses on the algebraic theory underlying the study of the complexity and the algorithms for the Constraint Satisfaction Problem (CSP). We unify, simplify, and extend parts of the three approaches that have been developed to study the CSP over finite templates – absorption theory that was used to characterize CSPs solvable by local consistency methods (JACM’14), and Bulatov’s and Zhuk’s theories that were used for two independent proofs of the CSP Dichotomy Theorem (FOCS’17, JACM’20).As the first contribution we present an elementary theorem about primitive positive definability and use it to obtain the starting points of Bulatov’s and Zhuk’s proofs as corollaries. As the second contribution we propose and initiate a systematic study of minimal Taylor algebras. This class of algebras is broad enough so that it suffices to verify the CSP Dichotomy Theorem on this class only, but still is unusually well behaved. In particular, many concepts from the three approaches coincide in the class, which is in striking contrast with the general setting.We believe that the theory initiated in this paper will eventually result in a simple and more natural proof of the Dichotomy Theorem that employs a simpler and more efficient algorithm, and will help in attacking complexity questions in other CSP-related problems.
@inproceedings{paperbot6217,
title = {Minimal Taylor Algebras as a Common Framework for the Three Algebraic Approaches to the CSP},
author = {Libor Barto and Zarathustra Brady and Andrei Bulatov and Marcin Kozik and Dmitriy Zhuk},
booktitle = {LICS},
year = {2021},
doi = {10.1109/lics52264.2021.9470557}
}