| EPSRC Reference: |
EP/G011001/1 |
| Title: |
Descriptive Complexity of Constraints: An Algebraic Approach |
| Principal Investigator: |
Krokhin, Professor A |
| Other Investigators: |
|
| Researcher Co-Investigators: |
|
| Project Partners: |
|
| Department: |
Computer Science |
| Organisation: |
Durham, University of |
| Scheme: |
Standard Research |
| Starts: |
17 September 2008 |
Ends: |
16 November 2010 |
Value (£): |
26,145
|
| 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 problems have been widely studied in computer science because they can model many computational problems. Such problems are computationally hard in general, but some restrictions may ensure lower complexity. Descriptive complexity of a problem is measured by the richness of logical language necessary to describe the problem. As is well known, low descriptive complexity (that is, definability in a relatively weak logical language) implies low computational complexity (that is, relatively small amount of computational resources necessary to solve the problem).We propose to study descriptive complexity of restricted constraint satisfaction problems using the logic programming language Datalog and its fragments. This should lead to a better understanding of constraint satisfaction problems that require a small amount of space to solve them. We plan to combine methods from algebra, logic, and combinatorics to characterise constraint satisfaction problems with low descriptive complexity.
|
|
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: |
|