EPSRC logo

Details of Grant 

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: