University of Leicester


The Algebraic Structure of Complexity Classes

Source of Funding: Engineering and Physical Sciences Research Council (EPSRC)
Amount: 43,619
Duration: January 1999 - December 2001
Principal Investigator: Prof. Iain Stewart
Other Investigators: Dr. Pete Jeavons (Royal Holloway, University of London), Dr. Dave Cohen (Royal Holloway, University of London)
Research Assistant: Mr. Richard Gault (Royal Holloway, University of London)
Ph.D. Student: Mr. Florent Madelaine

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 computational resources required for their solution. The study of complexity theory has recently been transformed by the discovery that there are close connections between the classical complexity classes and a variety of logics. Our research programme is prompted by the discovery of a similar relationship between the classical complexity classes and certain algebraic properties. There are three themes of research: can the tractable subsets of the interval algebra be identified using algebraic properties?; are there efficient algorithms for determining the algebraic properties of arbitrary relational structures?; and can the classical complexity classes be characterized as classes of relational structures satisfying certain algebraic properties?

University of Leicester 15th December 2000. Last modified: 8th January 2004, 14:32:13.
Informatics Web Maintainer. This document has been approved by the Head of Department.