Absorbing Subalgebras, Cyclic Terms, and the Constraint Satisfaction Problem
Absorbing Subalgebras, Cyclic Terms, and the Constraint Satisfaction Problem
复制标题
吸收子代数、循环项和约束满足问题
DOI：
--
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
M. Kozik
中科院分区：
文献类型：
--
作者：
L. Barto;M. Kozik
代数二分猜想指出，如果与模板相关联的多态代数位于泰勒簇中，则固定模板上的约束满足问题在多项式时间内可解，否则是NP完全的。本文给出了双生成Taylor簇的两个新刻画。第一个刻画是利用吸收子代数和第二个刻画是利用循环项。这些新的条件使我们能够以初等的和自包含的方式重新证明Bang-Jensen和Hell的猜想（作者证明）和局部有限Taylor簇的特征（McKenzie和Maroti证明）。
The Algebraic Dichotomy Conjecture states that the Constraint Satisfaction Problem over a fixed template is solvable in polynomial time if the algebra of polymor- phisms associated to the template lies in a Taylor variety, and is NP-complete otherwise. This paper provides two new characterizations of finitely generated Taylor varieties. The first characterization is using absorbing subalgebras and the second one cyclic terms. These new conditions allow us to reprove the conjecture of Bang-Jensen and Hell (proved by the authors) and the characterization of locally finite Taylor varieties using weak near- unanimity terms (proved by McKenzie and Maroti) in an elementary and self-contained way.