In the counting constraint satisfaction problem (#CSP), we wish to know how many ways there are to satisfy a given system of constraints on a set of variables, where a constraint is a relation chosen from a fixed finite set. This class is now known to have a decidable dichotomy, depending on the form of the relations. The dichotomy is that each problem in the class is either solvable in polynomial time (FP) or is hard (#P-complete), with no intermediate cases. The talk will give an introduction to the problem and its background, and outline a proof of the dichotomy theorem.
University of Leeds
Fri, 07/06/2013 - 2:00pm to 3:00pm
RC-4082, Red Centre Building, UNSW