Joint Colloquium: Dyer -- The counting constraint satisfaction problem

Speaker: Prof Martin Dyer 

http://www.comp.leeds.ac.uk/dyer/pub.shtml

Time: Friday, June 7, 2:00--3:00PM

Room: RC-4082 of the Red Centre, East Wing, UNSW


-----------------------------------------------

Title: The counting constraint satisfaction problem

Abstract:  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.

-----------------------------------------------

Joint Colloquium web site: 

http://www.maths.usyd.edu.au/u/SemConf/JointColloquium/index.html