Details of Grant 

EPSRC Reference:	GR/R29598/01
Title:	Algebraic Structural Methods and Complexity of Constraint Satisfaction
Principal Investigator:	Jeavons, Professor PG
Other Investigators:	Krokhin, Professor A
Researcher Co-Investigators:
Project Partners:
Department:	Computer Science
Organisation:	University of Oxford
Scheme:	Standard Research (Pre-FEC)
Starts:	14 May 2001	Ends:	13 August 2004	Value (£):	210,406
EPSRC Research Topic Classifications:	Algebra & Geometry Fundamentals of Computing Logic & Combinatorics
EPSRC Industrial Sector Classifications:	Information Technologies
Related Grants:
Panel History:
Summary on Grant Application Form
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.
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:	http://www.ox.ac.uk