论文标题
一致性间隔和含义的分离
Separation of congruence intervals and implications
论文作者
论文摘要
在计算机科学和数学的许多领域，已经对约束满意度问题（CSP）进行了深入研究。基于通用代数的工具，CSP的方法被证明是研究此问题的复杂性和算法的最成功的方法。在二十年中，已经开发了几种技术。其中之一是通过将边缘色图与代数相关联，并研究代数的性质与相关图的结构如何相关。在我们的前两篇论文中介绍了这种方法（A.Bulatov，Idempotent代数I，ii。Arxiv：2006.09599，Arxiv：2006.10239，2020，2020）。在本文中，我们通过引入有限的基本代数的新结构特性来进一步推进它，例如省略类型1，例如分离的一致性，崩溃的多项式及其对有限代数的细分产物结构的影响。本文还为我们的Feder-Vardi二分法猜想证明了代数背景（A. Bulatov，非均匀CSP的二分法定理。
The Constraint Satisfaction Problem (CSP) has been intensively studied in many areas of computer science and mathematics. The approach to the CSP based on tools from universal algebra turned out to be the most successful one to study the complexity and algorithms for this problem. Several techniques have been developed over two decades. One of them is through associating edge-colored graphs with algebras and studying how the properties of algebras are related with the structure of the associated graphs. This approach has been introduced in our previous two papers (A.Bulatov, Local structure of idempotent algebras I,II. arXiv:2006.09599, arXiv:2006.10239, 2020). In this paper we further advance it by introducing new structural properties of finite idempotent algebras omitting type 1 such as separation congruences, collapsing polynomials, and their implications for the structure of subdirect products of finite algebras. This paper also provides the algebraic background for our proof of Feder-Vardi Dichotomy Conjecture (A. Bulatov, A Dichotomy Theorem for Nonuniform CSPs. FOCS 2017: 319-330).
