The Complexity of Weighted Boolean #CSP with Mixed Signs

Details The Complexity of Weighted Boolean #CSP with Mixed Signs The Complexity of Weighted Boolean #CSP with Mixed Signs

2008-12-22

arxiv.org/abs/0812.4171v2

Computer Science

Computational Complexity

24 pages

Scientific paper

We give a complexity dichotomy for the problem of computing the partition function of a weighted Boolean constraint satisfaction problem. Such a problem is parameterized by a set of rational-valued functions, which generalize constraints. Each function assigns a weight to every assignment to a set of Boolean variables. Our dichotomy extends previous work in which the weight functions were restricted to being non-negative. We represent a weight function as a product of the form (-1)^s g, where the polynomial s determines the sign of the weight and the non-negative function g determines its magnitude. We show that the problem of computing the partition function (the sum of the weights of all possible variable assignments) is in polynomial time if either every weight function can be defined by a "pure affine" magnitude with a quadratic sign polynomial or every function can be defined by a magnitude of "product type" with a linear sign polynomial. In all other cases, computing the partition function is FP^#P-complete.

Affiliated with

Also associated with

No associations

Rating

The Complexity of Weighted Boolean #CSP with Mixed Signs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The Complexity of Weighted Boolean #CSP with Mixed Signs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Complexity of Weighted Boolean #CSP with Mixed Signs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-538938