The Complexity of Weighted Boolean #CSP
| dc.creator | Dyer, Martin | |
| dc.creator | Goldberg, Leslie Ann | |
| dc.creator | Jerrum, Mark | |
| dc.date | 2007-04-27 | |
| dc.date | 2008-06-19 | |
| dc.date.accessioned | 2026-07-07T12:44:27Z | |
| dc.date.available | 2026-07-07T12:44:27Z | |
| dc.description | 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 parameterised by a finite set F of non-negative 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 the partition function, i.e. the sum of the weights of all configurations, can be computed in polynomial time if either (1) every function in F is of ``product type'', or (2) every function in F is ``pure affine''. For every other fixed set F, computing the partition function is FP^{#P}-complete. | |
| dc.description | Minor revision | |
| dc.identifier | https://arxiv.org/abs/0704.3683 | |
| dc.identifier | http://arxiv.org/abs/0704.3683 | |
| dc.identifier | SIAM J. Comput. 38(5), 1970-1986 | |
| dc.identifier | doi:10.1137/070690201 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/220776 | |
| dc.subject | Computational Complexity | |
| dc.subject | Combinatorics | |
| dc.subject | F.2.2; F.4.1; G.2.1 | |
| dc.title | The Complexity of Weighted Boolean #CSP | |
| dc.type | text |