An approximation trichotomy for Boolean #CSP
An approximation trichotomy for Boolean #CSP
复制标题
布尔值的近似三分法
DOI：
10.1016/j.jcss.2009.08.003
复制
发表时间：
2010
影响因子：
1.1
通讯作者：
Dyer M
中科院分区：
文献类型：
--
作者：
Dyer M
对于布尔CSP实例的满足赋值数目的近似计数的复杂度，给出了一个三分定理。这类问题通过约束语言参数化，该语言指定约束中可能使用的关系。如果约束语言中的每个关系都是仿射的，则可以在多项式时间内精确地计算出满足分配的数量。否则，如果约束语言中的每个关系都在Post晶格的共克隆im2中，那么对于复杂度类#RHΠ1的保持近似约简，计算满足赋值的问题就完成了。这意味着对这样一个CSP实例的满足赋值的近似计数问题在复杂性上等同于其他几个已知的计数问题，包括对二部图中独立集的数量的近似计数问题。对于所有其他固定约束语言，问题对于#P来说是关于保持近似约简的完整的，这意味着除非NP=RP，否则不存在计数满足赋值的完全多项式随机化近似方案。
We give a trichotomy theorem for the complexity of approximately counting the number of satisfying assignments of a Boolean CSP instance. Such problems are parameterised by a constraint language specifying the relations that may be used in constraints. If every relation in the constraint language is affine then the number of satisfying assignments can be exactly counted in polynomial time. Otherwise, if every relation in the constraint language is in the co-clone IM2from Post's lattice, then the problem of counting satisfying assignments is complete with respect to approximation-preserving reductions for the complexity class #RHΠ1. This means that the problem of approximately counting satisfying assignments of such a CSP instance is equivalent in complexity to several other known counting problems, including the problem of approximately counting the number of independent sets in a bipartite graph. For every other fixed constraint language, the problem is complete for #P with respect to approximation-preserving reductions, meaning that there is no fully polynomial randomised approximation scheme for counting satisfying assignments unless NP=RP.
登录
查看更多内容
影响因子：
1.6
作者：
Feder, T;Vardi, MY
通讯作者：
Vardi, MY
DOI：
10.1137/070690201
发表时间：
2007-04
期刊：
SIAM J. Comput.
影响因子：
--
作者：
M. Dyer;L. A. Goldberg;M. Jerrum
通讯作者：
M. Dyer;L. A. Goldberg;M. Jerrum
DOI：
--
发表时间：
2005
期刊：
Electron. Colloquium Comput. Complex.
影响因子：
--
作者：
N. Creignou;Phokion G. Kolaitis;B. Zanuttini
通讯作者：
B. Zanuttini
布尔共克隆的基础
影响因子：
0.5
作者：
Elmar Böhler;S. Reith;Henning Schnoor;H. Vollmer
通讯作者：
H. Vollmer