The Complexity of Weighted Boolean #CSP

Understand

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.