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

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


If you are registered you may mark the scnews item as read.
School members may try to .