论文标题
强大的子代理和约束满意度问题
Strong subalgebras and the Constraint Satisfaction Problem
论文作者
论文摘要
在2007年，人们推测，当$γ$且仅当$γ$通过弱接近统一（WNU）的操作保留时，对约束语言$γ$的约束满意度问题（CSP）是可以处理的。经过多次努力和部分结果，安德烈·布拉托夫（Andrei Bulatov）和作者在2017年独立证明了这一猜想。在本文中，我们考虑了我证明的两种主要成分之一，即强有力的亚代词，使我们能够迭代地迭代变量域。为了解释这一想法的工作方式，我们显示了强大亚词法的代数特性，并提供了有关CSP复杂性的两个重要事实的独立证明。首先，我们证明，如果未通过WNU操作保留约束语言，则相应的CSP为NP-HARD。其次，我们表征可以通过局部一致性检查来解决的所有约束语言。此外，我们表征了所有没有wnu术语的所有基本代数$ n $，没有wnu术语，具有大于2的所有含义的wnu术语。本文中介绍的大多数结果并不新鲜，但我相信这篇文章可以帮助我了解我对CSP和已知的新自我验证的验证，也将有用。
In 2007 it was conjectured that the Constraint Satisfaction Problem (CSP) over a constraint language $Γ$ is tractable if and only if $Γ$ is preserved by a weak near-unanimity (WNU) operation. After many efforts and partial results, this conjecture was independently proved by Andrei Bulatov and the author in 2017. In this paper we consider one of two main ingredients of my proof, that is, strong subalgebras that allow us to reduce domains of the variables iteratively. To explain how this idea works we show the algebraic properties of strong subalgebras and provide self-contained proof of two important facts about the complexity of the CSP. First, we prove that if a constraint language is not preserved by a WNU operation then the corresponding CSP is NP-hard. Second, we characterize all constraint languages that can be solved by local consistency checking. Additionally, we characterize all idempotent algebras not having a WNU term of a concrete arity $n$, not having a WNU term, having WNU terms of all arities greater than 2. Most of the results presented in the paper are not new, but I believe this paper can help to understand my approach to CSP and the new self-contained proof of known facts will be also useful.
