On the complexity of #CSP
On the complexity of #CSP
复制标题
DOI：
10.1145/1806689.1806789
复制
发表时间：
2010-03
期刊：
影响因子：
--
通讯作者：
M. Dyer;David Richerby
中科院分区：
文献类型：
--
作者：
M. Dyer;David Richerby
Bulatov（2008）给出了计数约束满足问题的二分法#CSP。#CSP中的一个问题由约束语言γ表征，它是有限域上的一个固定的有限关系集。这个问题的一个实例使用这些关系来约束一组有限的变量所取的值。Bulatov证明，对于任何固定的γ，根据约束语言γ的结构，从#CSP计算任何问题的实例的满意分配的问题要么是多项式时间（FP）的，要么是#P-完全的。他的证明在很大程度上利用了泛代数的技术，如果没有对该领域的安全掌握，就无法理解。我们给一个基本的证明布拉托夫的二分法，简洁的表示，我们称之为框架，一类高度结构化的关系，我们称之为强矩形的基础上。我们表明，这些正是根据Mal'tsev多态性不变的关系。在途中，我们给出了一个简化的决策算法的强矩形约束语言由于Bulatov和Dalmau（2006）。除了Mal'tsev多态性的简单概念之外，Out证明不使用泛代数，并且对于#CSP背景不深的读者来说也是可以理解的。
Bulatov (2008) has given a dichotomy for the counting constraint satisfaction problem, #CSP. A problem from #CSP is characterized by a constraint language γ, which is a fixed, finite set of relations over a finite domain. An instance of the problem uses these relations to constrain the values taken by a finite set of variables. Bulatov showed that, for any fixed γ, the problem of counting the satisfying assignments of instances of any problem from #CSP is either in polynomial time (FP) or #P-complete, according on the structure of the constraint language γ. His proof draws heavily on techniques from universal algebra and cannot be understood without a secure grasp of that field. We give an elementary proof of Bulatov's dichotomy, based on succinct representations, which we call frames, of a class of highly structured relations, which we call strongly rectangular. We show that these are precisely the relations that are invariant under a Mal'tsev polymorphism. En route, we give a simplification of a decision algorithm for strongly rectangular constraint languages due to Bulatov and Dalmau (2006). Out proof uses no universal algebra, except for the straightforward concept of the Mal'tsev polymorphism and is accessible to readers with little background in #CSP.