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

Publications

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

publication icon
Dyer M (2009) Randomly coloring random graphs in Random Structures and Algorithms

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

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

publication icon
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