The Complexity of Counting in Constraint Satisfaction Problems
Lead Research Organisation:
University of Liverpool
Department Name: Computer Science
Abstract
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.
Organisations
People |
ORCID iD |
| Leslie Ann Goldberg (Principal Investigator) |
Publications
Bulatov A
(2012)
The complexity of weighted and unweighted #CSP
in Journal of Computer and System Sciences
Bulatov A
(2009)
The complexity of weighted Boolean #CSP with mixed signs
in Theoretical Computer Science
Dyer M
(2009)
The Complexity of Weighted Boolean #CSP
in SIAM Journal on Computing
Dyer M
(2010)
A Complexity Dichotomy For Hypergraph Partition Functions
in computational complexity
Dyer M
(2012)
The complexity of approximating bounded-degree Boolean #CSP
in Information and Computation
Dyer M
(2010)
An approximation trichotomy for Boolean #CSP
in Journal of Computer and System Sciences
Goldberg L
(2012)
Approximating the partition function of the ferromagnetic Potts model
in Journal of the ACM
Goldberg L
(2010)
The mixing time of Glauber dynamics for coloring regular trees
in Random Structures & Algorithms
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 |