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.


Martin Dyer

Research Area

University of Leeds


Fri, 07/06/2013 - 2:00pm to 3:00pm


RC-4082, Red Centre Building, UNSW