COOKIES: By using this website you agree that we can place Google Analytics Cookies on your device for performance monitoring. |

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

## The Complexity of #CSPAdd 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)
- Computer Laboratory talks
- Computing and Mathematics
- Logic and Semantics Seminar (Computer Laboratory)
- Room FW11, Computer Laboratory, William Gates Building
- School of Technology
- Trust & Technology Initiative - interesting events
- bld31
Note that ex-directory lists are not shown. |
## Other listsThinking Society: Is our university a place of free thinking? Churchill College Phoenix Society Mordell Lectures## Other talksReading and Panel Discussion with Emilia Smechowski Attentional episodes and cognitive control Breast cancer - demographics, presentation, diagnosis and patient pathway Localization and chiral splitting in scattering amplitudes My ceramic practice, and Moon Jars for the 21st century Well-posedness of weakly hyperbolic systems of PDEs in Gevrey regularity. |