| EPSRC Reference: |
EP/C54384X/1 |
| Title: |
Combining Approaches in Classifying Complexity of Constraints |
| Principal Investigator: |
Krokhin, Professor A |
| Other Investigators: |
|
| Researcher Co-Investigators: |
|
| Project Partners: |
|
| Department: |
Computer Science |
| Organisation: |
Durham, University of |
| Scheme: |
Standard Research (Pre-FEC) |
| Starts: |
15 September 2005 |
Ends: |
14 September 2008 |
Value (£): |
205,575
|
| EPSRC Research Topic Classifications: |
| Fundamentals of Computing |
Logic & Combinatorics |
|
| EPSRC Industrial Sector Classifications: |
| No relevance to Underpinning Sectors |
|
|
| Related Grants: |
|
| Panel History: |
| Panel Date | Panel Name | Outcome |
|
22 Mar 2005
|
EURYI Central Panel
|
Deferred
|
|
13 Apr 2005
|
ICT Fellowships 2005 Interview Panel
|
Deferred
|
|
11 Mar 2005
|
ICT Fellowships Sift Panel 2005
|
Deferred
|
|
|
Summary on Grant Application Form |
|
The proposed research concerns constraint satisfaction problems (CSPs). The aim in a constraint satisfaction problem is to find an assignment of values to a given set of variables, subject to constraints on the values which can be assigned to certain specified subsets of variables. This general setting allows one to express, in a natural way, a wide variety of problems encountered in Artificial Intelligence, Combinatorial Optimisation, Graph Theory, Logic Programming, Database Theory and elsewhere.The two main directions of research in CSP are as follows: one is Al-oriented and comprises modelling other problems as CSPs, empirical studies and constraint programming, while the other is Theoretical Computer Science-oriented and studies the structure and the complexity of fragments of CSP and its many variants. In this proposal, we follow the second direction.Solving constraint satisfaction problems in full generality is difficult, and it is very unlikely that general efficient algorithms for these problems exist. We propose to study which restrictions on the type of constraints allow one to efficiently solve four different useful versions of such problems. Due to the many ways in which constraint satisfaction problems can be viewed, many methods can be used to evaluate the complexity of these problems. We plan to combine methods from algebra, logic and combinatorics in our research.
|
|
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: |
|