EPSRC Reference: 
GR/M12933/01 
Title: 
THE ALGEBRAIC STRUCTURE OF COMPLEXITY CLASSES 
Principal Investigator: 
Stewart, Professor IA 
Other Investigators: 

Researcher CoInvestigators: 

Project Partners: 

Department: 
Mathematics 
Organisation: 
University of Leicester 
Scheme: 
Standard Research (PreFEC) 
Starts: 
01 January 1999 
Ends: 
31 December 2001 
Value (£): 
46,731

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 nonacademic 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.le.ac.uk 