Name
Abstract | ||
|---|---|---|
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 prob- lem 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 computing the partition function, i.e. the sum of the weights of all config- urations, is FP#P-complete unless either (1) every function in F is of "product type", or (2) every function in F is "pure affine". In the remaining cases, computing the partition function is in P. This paper gives a dichotomy theorem for the complexity of the partition function of weighted Boolean constraint satisfaction problems. Such problems are parameterised by a set F of non-negative functions that may be used to assign weights to configurations (solutions) of the instance. These functions take the place of the allowed constraint relations in classical constraint satisfaction problems (CSPs). Indeed, the classical setting may be recovered by restricting F to functions with range {0,1}. The key problem associated with an instance of a weighted CSP is to compute its partition function, i.e., the sum of weights of all its configurations. Computing the partition function of a weighted CSP may be viewed a gen- eralisation of counting the number of satisfying solutions of a classical CSP. Many partition functions from statistical physics may be expressed as weighted CSPs. For example, the Potts model (23) is naturally expressible as a weighted CSP, whereas in the classical frame- work only the "hard core" versions may be directly expressed. (The hard-core version of the antiferromagnetic Potts model corresponds to graph colouring and the hard-core version of the ferromagnetic Potts model is trivial — acceptable configurations colour the entire graph with a single colour.) A corresponding weighted version of the decision CSP was investigated by Cohen, Cooper, Jeavons and Krokhin (3). This results in optimisation problems. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1137/070690201 | Clinical Orthopaedics and Related Research |
Keywords | Field | DocType |
dichotomy theorem,weighted boolean constraint satisfaction,classical constraint satisfaction problem,1-valued function,problem instance,partition function,finite set,nonnegative function,feasible solution,sf fp,weighted boolean csp,value function,counting,constraint satisfaction problem,polynomial time,constraint satisfaction,p | Discrete mathematics,Constraint satisfaction,Combinatorics,Parameterized complexity,Finite set,Partition function (statistical mechanics),Constraint satisfaction problem,Partition (number theory),Mathematics,Special case | Journal |
Volume | Issue | ISSN |
38 | 5 | SIAM J. Comput. 38(5), 1970-1986 |
Citations | PageRank | References |
50 | 1.70 | 14 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Martin Dyer | 1 | 1029 | 97.62 |
| leslie ann goldberg | 2 | 1411 | 125.20 |
| mark jerrum | 3 | 2755 | 564.62 |