The Complexity of Weighted Boolean #CSP
The Complexity of Weighted Boolean #CSP
复制标题
DOI：
10.1137/070690201
复制
发表时间：
2007-04
期刊：
影响因子：
--
通讯作者：
M. Dyer;L. A. Goldberg;M. Jerrum
中科院分区：
文献类型：
--
作者：
M. Dyer;L. A. Goldberg;M. Jerrum
本文为计算加权布尔约束满意度问题的分区功能的复杂性提供了二分法定理。对于问题实例的配置（可行解决方案）。所有配置的权重的总和为$ \ text {{\ sf fp}}}}^{\ text {{{\ sf \ #p}}}} $ - 除非（1）$ \ Mathcal {f}中的每个函数，否则完成$是“产品类型”，或（2）$ \ Mathcal {f} $中的每个功能是“纯仿射”。
This paper gives a dichotomy theorem for the complexity of computing the partition function of an instance of a weighted Boolean constraint satisfaction problem. The problem is parameterized by a finite set $\mathcal{F}$ of nonnegative functions that may be used to assign weights to the configurations (feasible solutions) of a problem instance. Classical constraint satisfaction problems correspond to the special case of 0,1-valued functions. We show that computing the partition function, i.e., the sum of the weights of all configurations, is $\text{{\sf FP}}^{\text{{\sf\#P}}}$-complete unless either (1) every function in $\mathcal{F}$ is of “product type,” or (2) every function in $\mathcal{F}$ is “pure affine.” In the remaining cases, computing the partition function is in P.