Details of Grant 

EPSRC Reference:	GR/M12926/02
Title:	THE ALGEBRAIC STRUCTURE OF COMLEXITY CLASSES
Principal Investigator:	Jeavons, Professor PG
Other Investigators:
Researcher Co-Investigators:
Project Partners:
Department:	Computer Science
Organisation:	University of Oxford
Scheme:	Standard Research (Pre-FEC)
Starts:	01 September 1999	Ends:	31 December 2001	Value (£):	106,234
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
One of the fundamental insights arising from the study of computational complexity is that problems may be classified into separate complexity classes according to the amount of computational resources (typically time and space) which are required to solve them.The study of computational complexity theory has recently been transformed by the discovery that there are close connections between the classical complexity classes and various forms of logic. The research programme described here is prompted by the discovery of a similar relationship between the classical complexity classes and certain algebraic properties. The research proposal seeks to apply these novel connections between complexity theory and algebra to a new problem area, and to further develop the interaction between these two fields.The proposed research is divided into three research themes: scheduling problems, computational techniques, and extending the underlying theory. The central questions to be addressed in these themes are as follows:1. Can the tractable subsets of the interval algebra be identified using algebraic properties?2. Are there efficient algorithms for determining the algebraic properties of arbitrary relational structures?3. Can the classical complexity classes be characterised as classes of relational structures satisfying certain algebraic properties?
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