The Complexity of Counting in Constraint Satisfaction Problems
Lead Research Organisation:
University of Leeds
Department Name: Sch of Computing
Abstract
Constraint Satisfaction, which originated in Artificial Intelligence,provides a general framework for modelling decision problems, and hasmany practical applications. Decisions are modelled by variables, which aresubject to constraints, modelling logical and resource restrictions. Theparadigm 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 amajor and active area within computational complexity.The overall goal is to classify CSPs according to complexity, giving acharacterisation for which CSPs are tractable.We will focus especially on characterizing the complexityof counting in Constraint Satisfaction problems.Specifically, we will study the complexity of exactly counting
Organisations
People |
ORCID iD |
| Martin Edward Dyer (Principal Investigator) |
Publications
Bulatov A
(2009)
The complexity of weighted Boolean #CSP with mixed signs
in Theoretical Computer Science
Dyer M
(2013)
An Effective Dichotomy for the Counting Constraint Satisfaction Problem
in SIAM Journal on Computing
Dyer M
(2010)
An approximation trichotomy for Boolean #CSP
in Journal of Computer and System Sciences
Dyer M
(2012)
The complexity of approximating bounded-degree Boolean #CSP
in Information and Computation
Dyer M
(2010)
Randomly coloring random graphs Randomly Coloring Random Graphs
in Random Structures & Algorithms
Dyer M
(2010)
On the complexity of #CSP
Dyer M
(2009)
The Complexity of Weighted Boolean #CSP
in SIAM Journal on Computing
| Description | They have led to a stream of research by other academics in theoretical computer science. |
| First Year Of Impact | 2008 |
| Sector | Education |
| Impact Types | Cultural |