|
| EPSRC Reference: |
GR/M12926/02 |
| Title: |
THE ALGEBRAIC STRUCTURE OF COMLEXITY CLASSES |
| Principal Investigator: |
Professor PG Jeavons |
| Other Investigators: |
|
| Researcher Co-investigator: |
|
| Project Partner: |
|
| Department: |
Computing Laboratory |
| Organisation: |
University of Oxford |
| Scheme: |
Standard Research |
| Starts: |
01 September 1999 |
Ends: |
31 December 2001 |
Value (£): |
106,234
|
| EPSRC Research Topic Classifications: |
|
| EPSRC Industrial Sector Classifications: |
| No relevance to Underpinning Sectors |
|
|
| Related Grants: |
|
| Panel History: |
|
|
Summary |
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?
|
| Final Report Summary |
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?
|
| Further Information: |
|
| Organisation Website: |
http://www.ox.ac.uk |
|
|