The Complexity of Counting in Constraint Satisfaction Problems
Lead Research Organisation:
Queen Mary University of London
Department Name: Sch of Mathematical Sciences
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.
Publications
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
(2010)
An approximation trichotomy for Boolean #CSP
in Journal of Computer and System Sciences
Goldberg L
(2010)
A Complexity Dichotomy for Partition Functions with Mixed Signs
in SIAM Journal on Computing
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
| Description | Partition functions arise in statistical physics, for example in the study of spin systems. A spin system is described by a graph. A configuration of a spin system is an assignment of values or "spins" to the vertices of the graph. Adjacent spins interact, and a configuration has a well defined weight depending on the total effect of these interactions. The sum, over all configurations, of the weights of those configurations is the partition function of the spin system; it encodes much useful information about the system. Since the number of configurations grows exponentially as a function of the size of the underlying graph, it is a challenge to compute the partition function. Often the partition function is computationally intractable, but sometimes the combinatorial explosion have be avoided through the use of clever algorithms. The situation was already well understood when interactions are positive real numbers, so that the classification of partition functions into computationally tractable and intractable was precisely known. The article (*) was one of the main outputs of the EPSRC-funded project, and extended the classification to arbitrary real interactions. The introduction of negative weights leads to substantial technical challenges. Subsequently, the ideas in the paper were taken up by other researchers, leading, for example, to the further extension to complex weights by Cai, Chen and Lu. Complex weights would be relevant in the study of quantum systems. There were several other findings from the project, but (*) is both characteristic and substantial in its impact on the area. (*) A complexity dichotomy for partition functions with mixed signs Leslie Ann Goldberg, Martin Grohe, Mark Jerrum and Marc Thurley, SIAM Journal on Computing 39 (2010), 3336-3402. DOI 10.1137/090757496. |
| Exploitation Route | As mentioned above, our work has already prompted further advances in the classification of the computational complexity of partition functions, and beyond that to counting constraint satisfaction problems (#CSPs), e.g., Cai and Chen's dichotomy for complex weighted #CSPs. |
| Sectors | Other |
| URL | http://www.maths.qmul.ac.uk/~mj/pubs.html |