Complexity of Counting CSP with Complex Weights

Details Complexity of Counting CSP with Complex Weights Complexity of Counting CSP with Complex Weights

2011-11-10

arxiv.org/abs/1111.2384v1

Computer Science

Computational Complexity

Scientific paper

We give a complexity dichotomy theorem for the counting Constraint Satisfaction Problem (#CSP in short) with complex weights. To this end, we give three conditions for its tractability. Let F be any finite set of complex-valued functions, then we prove that #CSP(F) is solvable in polynomial time if all three conditions are satisfied; and is #P-hard otherwise. Our complexity dichotomy generalizes a long series of important results on counting problems: (a) the problem of counting graph homomorphisms is the special case when there is a single symmetric binary function in F; (b) the problem of counting directed graph homomorphisms is the special case when there is a single not-necessarily-symmetric binary function in F; and (c) the standard form of #CSP is when all functions in F take values in {0,1}.

Affiliated with

Also associated with

No associations

Rating

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

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-727661