|
| EPSRC Reference: |
GR/R22704/01 |
| Title: |
Algebraic Structural Methods and Complexity of Constraint Satisfaction: An Initial Study |
| Principal Investigator: |
Professor PG Jeavons |
| Other Investigators: |
|
| Researcher Co-investigator: |
|
| Project Partner: |
|
| Department: |
Computing Laboratory |
| Organisation: |
University of Oxford |
| Scheme: |
Standard Research |
| Starts: |
12 March 2001 |
Ends: |
11 June 2001 |
Value (£): |
10,170
|
| EPSRC Research Topic Classifications: |
| Algebra and Geometry |
Fundamentals of Computing |
|
| EPSRC Industrial Sector Classifications: |
| No relevance to Underpinning Sectors |
|
|
| Related Grants: |
|
| Panel History: |
|
|
Summary |
This proposal is for a Visiting Fellowship for a period of 3 months to enable Dr Krokhin of Ural State University, Russia, to work with Dr Peter Jeavons at the University of Oxford. Dr Krokhin is a specialist in algebra, and especially the theory of clones, and this project is designed to explore how results from algebraic clone theory can be used in the study of the family of computational problems known as "constraint satisfaction problems". This family of problems has been widely studied in computer science, and there have been many attempts to characterise restrictions on the general problem which make it possible to solve it efficiently. It appears that further progress with this difficult question could be made by using results from algebraic clone theory, and this project will begin to explore that possibility. One novel feature of the approach is that it includes both finite constraint satisfaction problems (such as graph colouring problems, and scheduling problems) and infinite constraint satisfaction problems (such as temporal and spatial reasoning problems). By taking an abstract, algebraic approach we hope to find a framework which incorporates both types of problems (which have traditionally been studied separately) and so obtain a better description of the computational complexity of these important problems.
|
| Final Report Summary |
This proposal is for a Visiting Fellowship for a period of 3 months to enable Dr Krokhin of Ural State University, Russia, to work with Dr Peter Jeavons at the University of Oxford. Dr Krokhin is a specialist in algebra, and especially the theory of clones, and this project is designed to explore how results from algebraic clone theory can be used in the study of the family of computational problems known as "constraint satisfaction problems". This family of problems has been widely studied in computer science, and there have been many attempts to characterise restrictions on the general problem which make it possible to solve it efficiently. It appears that further progress with this difficult question could be made by using results from algebraic clone theory, and this project will begin to explore that possibility. One novel feature of the approach is that it includes both finite constraint satisfaction problems (such as graph colouring problems, and scheduling problems) and infinite constraint satisfaction problems (such as temporal and spatial reasoning problems). By taking an abstract, algebraic approach we hope to find a framework which incorporates both types of problems (which have traditionally been studied separately) and so obtain a better description of the computational complexity of these important problems.
|
| Further Information: |
|
| Organisation Website: |
http://www.ox.ac.uk |
|
|