BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.cam.ac.uk//v3//EN
BEGIN:VTIMEZONE
TZID:Europe/London
BEGIN:DAYLIGHT
TZOFFSETFROM:+0000
TZOFFSETTO:+0100
TZNAME:BST
DTSTART:19700329T010000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=-1SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0100
TZOFFSETTO:+0000
TZNAME:GMT
DTSTART:19701025T020000
RRULE:FREQ=YEARLY;BYMONTH=10;BYDAY=-1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
CATEGORIES:Logic and Semantics Seminar (Computer Laboratory)
SUMMARY:The Complexity of #CSP - David Richerby\, Universi
ty of Liverpool
DTSTART;TZID=Europe/London:20110520T140000
DTEND;TZID=Europe/London:20110520T150000
UID:TALK31175AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/31175
DESCRIPTION:In the counting constraint satisfaction problem (#
CSP)\, we wish to compute the number of satisfying
assignments to a system of relational constraints
. Obviously\, this is at least as hard as determi
ning whether there is at least one satisfying assi
gnment\, which is already NP-complete in general a
s it includes 3-SAT and 3-colourability.\n\nBut if
we fix a "constraint language" (a list of specifi
c relations that may be used to define constraints
)\, the problem may become easier: for example\, t
here are constraint languages equivalent to 2-SAT
and 2-colourability. In 2008\, Andrei Bulatov sho
wed that\, for any fixed constraint language\, #CS
P is either computable in polynomial time or is NP
-hard (actually\, #P-complete). However\, his pro
of is very long and makes deep use of universal al
gebra\, making it hard to understand for people wh
o are not specialists in that field. It was also
left open whether the criterion for the dichotomy
is decidable.\n\nIn the talk\, I will sketch a new
proof of this dichotomy\, based just on elementar
y combinatorics\, and show that the resulting crit
erion is decidable in NP. No knowledge of CSP or
universal algebra will be assumed.\n\nJoint work w
ith Martin Dyer (University of Leeds).
LOCATION:Room FW11\, Computer Laboratory\, William Gates Bu
ilding
CONTACT:Bjarki Holm
END:VEVENT
END:VCALENDAR