University of Cambridge > > Logic and Semantics Seminar (Computer Laboratory) > The Complexity of #CSP

The Complexity of #CSP

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

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.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.


© 2006-2019, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity