The Complexity of Weighted Boolean #CSP

Details The Complexity of Weighted Boolean #CSP The Complexity of Weighted Boolean #CSP

2007-04-27

arxiv.org/abs/0704.3683v2

SIAM J. Comput. 38(5), 1970-1986

Computer Science

Computational Complexity

Minor revision

Scientific paper

10.1137/070690201

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.

Affiliated with

Also associated with

No associations

Rating

The Complexity of Weighted Boolean #CSP 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, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Complexity of Weighted Boolean #CSP will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-677235