The Complexity of #CSP

Add to your list(s) Download to your calendar using vCal

• David Richerby, University of Liverpool
• Friday 20 May 2011, 14:00-15:00
• Room FW11, Computer Laboratory, William Gates Building.

If you have a question about this talk, please contact Bjarki Holm.

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 determining whether there is at least one satisfying assignment, which is already NP-complete in general as it includes 3-SAT and 3-colourability.

But if we fix a “constraint language” (a list of specific relations that may be used to define constraints), the problem may become easier: for example, there are constraint languages equivalent to 2-SAT and 2-colourability. In 2008, Andrei Bulatov showed that, for any fixed constraint language, #CSP is either computable in polynomial time or is NP-hard (actually, #P-complete). However, his proof is very long and makes deep use of universal algebra, making it hard to understand for people who are not specialists in that field. It was also left open whether the criterion for the dichotomy is decidable.

In the talk, I will sketch a new proof of this dichotomy, based just on elementary combinatorics, and show that the resulting criterion is decidable in NP. No knowledge of CSP or universal algebra will be assumed.

Joint work with Martin Dyer (University of Leeds).

This talk is part of the Logic and Semantics Seminar (Computer Laboratory) series.

This talk is included in these lists:

• All Talks (aka the CURE list)
• Cambridge talks
• Computing and Mathematics
• Department of Computer Science and Technology talks and seminars
• Interested Talks
• Logic and Semantics Seminar (Computer Laboratory)
• Room FW11, Computer Laboratory, William Gates Building
• School of Technology
• Trust & Technology Initiative - interesting events
• bld31
• tcw57’s list
• yk373's list

Note that ex-directory lists are not shown.