Non-negative Weighted #CSPs: An Effective Complexity Dichotomy

Details Non-negative Weighted #CSPs: An Effective Complexity Dichotomy Non-negative Weighted #CSPs: An Effective Complexity Dichotomy

2010-12-27

arxiv.org/abs/1012.5659v1

Computer Science

Computational Complexity

Scientific paper

We prove a complexity dichotomy theorem for all non-negative weighted counting Constraint Satisfaction Problems (CSP). This caps a long series of important results on counting problems including unweighted and weighted graph homomorphisms and the celebrated dichotomy theorem for unweighted #CSP. Our dichotomy theorem gives a succinct criterion for tractability. If a set F of constraint functions satisfies the criterion, then the counting CSP problem defined by F is solvable in polynomial time; if it does not satisfy the criterion, then the problem is #P-hard. We furthermore show that the question of whether F satisfies the criterion is decidable in NP. Surprisingly, our tractability criterion is simpler than the previous criteria for the more restricted classes of problems, although when specialized to those cases, they are logically equivalent. Our proof mainly uses Linear Algebra, and represents a departure from Universal Algebra, the dominant methodology in recent years.

Affiliated with

Also associated with

No associations

Rating

Non-negative Weighted #CSPs: An Effective Complexity Dichotomy 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 Non-negative Weighted #CSPs: An Effective Complexity Dichotomy, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Non-negative Weighted #CSPs: An Effective Complexity Dichotomy will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-427427