SMS scnews item created by Alexander Fish at Fri 31 May 2013 1222
Type: Seminar
Modified: Fri 31 May 2013 1229
Distribution: World
Calendar1: 7 Jun 2013 1400-1500
CalLoc1: UNSW Red Centre 4082
Auth: afish@p617.pc (assumed)

Joint Colloquium: Dyer -- The counting constraint satisfaction problem

Speaker: Prof Martin Dyer

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: