| EPSRC Reference: |
EP/E062172/1 |
| Title: |
The Complexity of Counting in Constraint Satisfaction Problems |
| Principal Investigator: |
Dyer, Professor ME |
| Other Investigators: |
|
| Researcher Co-Investigators: |
|
| Project Partners: |
|
| Department: |
Sch of Computing |
| Organisation: |
University of Leeds |
| Scheme: |
Standard Research |
| Starts: |
01 October 2007 |
Ends: |
30 September 2010 |
Value (£): |
190,177
|
| EPSRC Research Topic Classifications: |
| Fundamentals of Computing |
|
|
| EPSRC Industrial Sector Classifications: |
| No relevance to Underpinning Sectors |
|
|
| Related Grants: |
|
| Panel History: |
|
|
Summary on Grant Application Form |
|
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
|
|
Key Findings |
|
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
|
|
Potential use in non-academic contexts |
|
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
|
|
Impacts |
|
| Description |
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk |
| Summary |
|
| Date Materialised |
|
|
|
|
Sectors submitted by the Researcher |
|
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
|
| Project URL: |
|
| Further Information: |
|
| Organisation Website: |
http://www.leeds.ac.uk |