Output details
11 - Computer Science and Informatics
University of Leeds
An Effective Dichotomy for the Counting Constraint Satisfaction Problem
<10>This paper proves a decidable complexity dichotomy for counting constraint satisfaction problems. Bulatov (2008) had given a much more complicated proof, without decidability. This paper gives an elementary proof of a new criterion for the dichotomy, and shows its decidability. An earlier conference version appeared in STOC2010 (ACM Symposium on Theory of Computing, one of the best two in computer science theory), was selected for a special edition of SIAM Journal on Computing (one of the two best in computer science theory). The proof techniques have generated further results, including a generalisation by Cai and Chen (STOC2012) to complex-weighted problems.