|
| EPSRC Reference: |
GR/R29598/01 |
| Title: |
Algebraic Structural Methods and Complexity of Constraint Satisfaction |
| Principal Investigator: |
Professor PG Jeavons |
| Other Investigators: |
|
| Researcher Co-investigator: |
|
| Project Partner: |
|
| Department: |
Computing Laboratory |
| Organisation: |
University of Oxford |
| Scheme: |
Standard Research |
| Starts: |
14 May 2001 |
Ends: |
13 August 2004 |
Value (£): |
210,406
|
| EPSRC Research Topic Classifications: |
| Algebra and Geometry |
Fundamentals of Computing |
| Logic and Combinatorics |
|
|
| EPSRC Industrial Sector Classifications: |
|
| Related Grants: |
|
| Panel History: |
|
|
Summary |
This proposal will enable Dr Bulatov and Dr Krokhin of Ural State University, Russia, to work with Dr Peter Jeavons at the University of Oxford. Dr Bulatov and Dr Krokhin are specialists in algebra, and especially the theory of clones and universal algebra, and this project is designed to explore how recent results and methods from universal algebra can be linked to the study of the broad 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 considerable further progress with this question could now be made by using structural results from universal algebra, and this project will develop the necessary theory. One novel feature of the approach is that it includes both finite constraint satisfaction problems (such as graph colouring problems, and satisfiability problems) and infinite constraint satisfaction problems (such as temporal and spatial reasoning problems). By taking an abstract, algebraic, approach we plan to develop a framework which naturally incorporates both types of problems (which have traditionally been studied separately) and so obtain a more powerful theory of the computational complexity of these important problems.
|
| Final Report Summary |
This proposal will enable Dr Bulatov and Dr Krokhin of Ural State University, Russia, to work with Dr Peter Jeavons at the University of Oxford. Dr Bulatov and Dr Krokhin are specialists in algebra, and especially the theory of clones and universal algebra, and this project is designed to explore how recent results and methods from universal algebra can be linked to the study of the broad 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 considerable further progress with this question could now be made by using structural results from universal algebra, and this project will develop the necessary theory. One novel feature of the approach is that it includes both finite constraint satisfaction problems (such as graph colouring problems, and satisfiability problems) and infinite constraint satisfaction problems (such as temporal and spatial reasoning problems). By taking an abstract, algebraic, approach we plan to develop a framework which naturally incorporates both types of problems (which have traditionally been studied separately) and so obtain a more powerful theory of the computational complexity of these important problems.
Project outcome
This project has firmly established the algebraic approach to constraints as an exciting and productive area of research on the boundary between computer science and mathematics. Most of the specific questions posed in the original proposal have been answered, including a complete classification of complexity for constraints over a finite domain with 3-elements, and a complete classification of complexity for the most popular framework for temporal reasoning, known as Allen's Interval Algebra.
As well as answering these questions the investigators have broadened the algebraic techniques they have developed to apply to a much wider range of problems, including quantified constraint problems, counting the number of solutions to a constraint problem, and soft constraint problems. Work on the complexity of soft constraint problems is now continuing with additional EPSRC support.
This work is attracting interest from both the mathematics and computer science research communities and the investigators have given a number of invited talks at international conferences addressing both communities.
|
| Further Information: |
|
| Organisation Website: |
http://www.ox.ac.uk |
|
|