论文标题
约束满意度问题对有限结构
Constraint Satisfaction Problems over Finite Structures
论文作者
论文摘要
我们对可能包含关系和操作的有限结构的约束满意度问题（CSP）的计算复杂性进行了系统的研究。我们显示了这个问题与自然代数问题之间的紧密联系：哪些有限代数仅接受多个同构的同态？我们提供了一些有限代数拥有此属性的足够和一些必要条件。特别是，我们表明，每个有限的方程式非平凡的代数都具有该特性，这使我们很容易对CSP进行完全的复杂性分类，从而在两元素结构上对CSP进行了完全的复杂性分类，从而扩展了Schaefer（Stoc'78）对两元素关系结构的分类。我们还介绍了宽度但没有关系宽度的两元素结构的例子（2,3），从而证明，从描述性复杂性的角度来看，可以使操作导致更丰富的理论。
We initiate a systematic study of the computational complexity of the Constraint Satisfaction Problem (CSP) over finite structures that may contain both relations and operations. We show the close connection between this problem and a natural algebraic question: which finite algebras admit only polynomially many homomorphisms into them? We give some sufficient and some necessary conditions for a finite algebra to have this property. In particular, we show that every finite equationally nontrivial algebra has this property which gives us, as a simple consequence, a complete complexity classification of CSPs over two-element structures, thus extending the classification for two-element relational structures by Schaefer (STOC'78). We also present examples of two-element structures that have bounded width but do not have relational width (2,3), thus demonstrating that, from a descriptive complexity perspective, allowing operations leads to a richer theory.
