The Algebraic Structure of Complexity Classes
Source of Funding: Engineering and Physical Sciences
Research Council (EPSRC)
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?