The Complexity of Counting in Constraint Satisfaction Problems

Lead Research Organisation: University of Liverpool
Department Name: Computer Science


Constraint Satisfaction, which originated in Artificial Intelligence, provides a general framework for modelling decision problems, and has many practical applications. Decisions are modelled by variables, which are subject to constraints, modelling logical and resource restrictions. The paradigm is sufficiently broad that many interesting problems can be modelled, from satisfiability problems to scheduling problems and graph-theory problems. Understanding the complexity of constraint satisfaction problems has become a major and active area within computational complexity. The overall goal is to classify CSPs according to complexity, giving a characterisation for which CSPs are tractable. We will focus especially on characterizing the complexity of counting in Constraint Satisfaction problems. Specifically, we will study the complexity of exactly counting CSP solutions, approximately counting CSP solutions, and sampling CSP solutions from appropriately-defined probability distributions. These important questions are closely related, and are strongly connected to questions in statistical physics.


10 25 50
publication icon
Bulatov A (2012) The complexity of weighted and unweighted #CSP in Journal of Computer and System Sciences

publication icon
Bulatov A (2009) The complexity of weighted Boolean #CSP with mixed signs in Theoretical Computer Science

publication icon
Dyer M (2010) A Complexity Dichotomy For Hypergraph Partition Functions in computational complexity

publication icon
Dyer M (2009) The Complexity of Weighted Boolean #CSP in SIAM Journal on Computing

publication icon
Dyer M (2012) The complexity of approximating bounded-degree Boolean #CSP in Information and Computation

publication icon
Dyer M (2010) An approximation trichotomy for Boolean #CSP in Journal of Computer and System Sciences

publication icon
Goldberg L (2010) The mixing time of Glauber dynamics for coloring regular trees in Random Structures and Algorithms

publication icon
Goldberg L (2010) A Complexity Dichotomy for Partition Functions with Mixed Signs in SIAM Journal on Computing

Description This grant resulted in improved knowledge about which counting
constraint satisfaction problems can be solved, and which are inherently intractable. It resulted in 10 scientific papers
published in high-quality venues.
Exploitation Route Our research results have been used and built upon by other
researchers in the area.
Sectors Digital/Communication/Information Technologies (including Software),Education