Abstract

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).