Complexity of Counting CSP with Complex Weights

We give a complexity dichotomy theorem for the counting constraint satisfaction problem (#CSP in short) with algebraic complex weights. To this end, we give three conditions for its tractability. Let F be any finite set of complex-valued functions. We show that #CSP(F) is solvable in polynomial time if all three conditions are satisfied; and is #P-hard otherwise. Our dichotomy theorem generalizes a long series of important results on counting problems: (a) the problem of counting graph homomorphisms is the special case when F has a single symmetric binary function [12, 5, 16, 8]; (b) the problem of counting directed graph homomorphisms is the special case when F has a single but not-necessarily-symmetric binary function [11, 6]; (c) the unweighted form of #CSP is when all functions in F take values in f0; 1g [2, 13, 14].