Constraint Satisfaction Problems and Finite Algebras
Constraint Satisfaction Problems and Finite Algebras
复制标题
约束满足问题和有限代数
DOI：
10.1007/3-540-45022-x_24
复制
发表时间：
2000
影响因子：
1.2
通讯作者：
P. Jeavons
中科院分区：
文献类型：
--
作者：
A. Bulatov;A. Krokhin;P. Jeavons
许多自然的组合问题可以表示为约束满足问题。这类问题通常是NP完全的，但对约束形式的某些限制可以确保可处理性。在本文中，我们表明，任何限制的约束类型的集合可以与一个有限的泛代数。我们探讨如何计算复杂性的限制约束满足问题连接到相应的代数的属性。利用这些结果，我们表现出一个共同的结构特性，所有已知的棘手的约束满足问题。最后，我们根据易处理性对有限严格单满射代数进行了分类。结果是一个二分法定理显着概括谢弗的二分法的广义可满足性问题。
Many natural combinatorial problems can be expressed as constraint satisfaction problems. This class of problems is known to be NP-complete in general, but certain restrictions on the form of the constraints can ensure tractability. In this paper we show that any restricted set of constraint types can be associated with a finite universal algebra. We explore how the computational complexity of a restricted constraint satisfaction problem is connected to properties of the corresponding algebra. Using these results we exhibit a common structural property of all known intractable constraint satisfaction problems. Finally, we classify all finite strictly simple surjective algebras with respect to tractability. The result is a dichotomy theorem which significantly generalises Schaefer's dichotomy for the Generalised Satisfiability problem.