The complexity of approximating conservative counting CSPs
The complexity of approximating conservative counting CSPs
复制标题
DOI：
10.1016/j.jcss.2014.06.006
复制
发表时间：
2012-08
期刊：
影响因子：
--
通讯作者：
X. Chen;M. Dyer;L. A. Goldberg;M. Jerrum;P. Lu;Colin McQuillan;David Richerby
中科院分区：
文献类型：
--
作者：
X. Chen;M. Dyer;L. A. Goldberg;M. Jerrum;P. Lu;Colin McQuillan;David Richerby
研究了近似加权计数约束满足问题CSP（F）的复杂性.在保守的情况下，F包含所有一元函数，分类是已知的布尔域，我们将其扩展到任意有限域。证明了如果F是“弱对数模”，则# CSP（F）在FP中.否则，它至少和BIS（在二分图中计算独立集）一样难以近似。BIS对于复杂度类# R H 1是完备的，并且被认为是难以处理的。我们进一步细分了#BIS-困难的情况：如果F是“弱对数超模”，# CSP（F）就像布尔对数超模加权# CSP一样容易;否则，我们证明它是NP-困难的近似。最后，我们给出了arity-2情况下的一个完整的可分性：# CSP（F）在FP中，是#BIS等价的，或者等价于# SAT（近似计算布尔CNF公式的满足赋值）。我们还讨论了我们的分类算法方面。
We study the complexity of the approximate weighted counting constraint satisfaction problem# CSP (F). In the conservative case, where F contains all unary functions, a classification is known over the Boolean domain; we extend this to arbitrary finite domains. We show that if F is “weakly log-modular”, then# CSP (F) is in FP. Otherwise, it is at least as difficult to approximate as# BIS (counting independent sets in bipartite graphs).# BIS is complete for the complexity class# R H Π 1, and believed to be intractable. We further sub-divide the# BIS-hard case: if F is “weakly log-supermodular”,# CSP (F) is as easy as a Boolean log-supermodular weighted# CSP; otherwise, we show that it is NP-hard to approximate. Finally, we give a full trichotomy for the arity-2 case:# CSP (F) is in FP, is# BIS-equivalent, or is equivalent to# SAT (approximately counting the satisfying assignments of Boolean CNF formulas). We also discuss algorithmic aspects of our classification.