Type: Seminar

Modified: Fri 31 May 2013 1229

Distribution: World

Auth: afish@p617.pc (assumed)

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