An Effective Dichotomy for the Counting Constraint Satisfaction Problem
An Effective Dichotomy for the Counting Constraint Satisfaction Problem
复制标题
DOI：
10.1137/100811258
复制
发表时间：
2010-03
期刊：
影响因子：
--
通讯作者：
M. Dyer;David Richerby
中科院分区：
文献类型：
--
作者：
M. Dyer;David Richerby
拉托夫[$35$TH国际自动机、语言和编程学术讨论会(第一部分)，计算机讲稿。SCI。5125，Springer，New York，2008，pp.646--661]给出了计数约束满足问题的二分法。CSP中的问题用约束语言$Gamma$来刻画，它是有限区域$D上的一组固定的有限关系。该问题的一个实例使用这些关系来约束任意大的有限变量集。Bulatov证明了计算CSP问题中任一问题实例的满意赋值的问题要么是多项式时间(FP)的，要么是P-完全的。他的证明在很大程度上借鉴了普适代数的技巧，如果没有对该领域的可靠把握，就不可能被理解。基于一类称为强矩形的高结构关系的简洁表示，我们给出了布拉托夫二分法的一个初等证明。我们证明了这些恰恰是……
Bulatov [Proceedings of the $35$th International Colloquium on Automata, Languages and Programming (Part 1), Lecture Notes in Comput. Sci. 5125, Springer, New York, 2008, pp. 646--661] gave a dichotomy for the counting constraint satisfaction problem \#CSP. A problem from \#CSP is characterized by a constraint language $\Gamma\!$, a fixed, finite set of relations over a finite domain $D$. An instance of the problem uses these relations to constrain an arbitrarily large finite set of variables. Bulatov showed that the problem of counting the satisfying assignments of instances of any problem from \#CSP is either in polynomial time (FP) or is \#P-complete. 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 relation...