An Effective Dichotomy for the Counting Constraint Satisfaction Problem

Details An Effective Dichotomy for the Counting Constraint Satisfaction Problem An Effective Dichotomy for the Counting Constraint Satisfaction Problem

2010-03-19

arxiv.org/abs/1003.3879v4

Computer Science

Computational Complexity

31 pages. Corrected some errors from previous versions

Scientific paper

Bulatov (2008) gave a dichotomy for the counting constraint satisfaction problem #CSP. A problem from #CSP is characterised by a constraint language, which is a fixed, finite set of relations over a finite domain D. An instance of the problem uses these relations to constrain the variables in a larger set. Bulatov showed that the problem of counting the satisfying assignments of instances of any problem from #CSP is either in polynomial time (FP) or is #P-complete. His proof draws heavily on techniques from universal algebra and cannot be understood without a secure grasp of that field. We give an elementary proof of Bulatov's dichotomy, based on succinct representations, which we call frames, of a class of highly structured relations, which we call strongly rectangular. We show that these are precisely the relations which are invariant under a Mal'tsev polymorphism. En route, we give a simplification of a decision algorithm for strongly rectangular constraint languages, due to Bulatov and Dalmau (2006). We establish a new criterion for the #CSP dichotomy, which we call strong balance, and we prove that this property is decidable. In fact, we establish membership in NP. Thus, we show that the dichotomy is effective, resolving the most important open question concerning the #CSP dichotomy.

Affiliated with

Also associated with

No associations

Rating

An Effective Dichotomy for the Counting Constraint Satisfaction Problem 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 An Effective Dichotomy for the Counting Constraint Satisfaction Problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and An Effective Dichotomy for the Counting Constraint Satisfaction Problem will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-126930