Copenhagen Programming Language Seminar


Complexity-Theoretic Hierarchies

Lars Kristiansen,
Oslo University College, Norway

Thursday, March 30, 15:15-16:00
DIKU, Universitetsparken 1, room N034


I will present two hierarchies of unknown ordinal height. Many of the well-known deterministic complexity classes, e.g. LOGSPACE, P, PSPACE, LINSPACE and EXPTIME, can be found in the hierarchies. These classes are defined by imposing explicit resource bounds on Turing machines, but note that the classes are not uniformly defined as some are defined by imposing time bounds, whereas other are defined by imposing space bounds. Small subrecursive classes can also be found in the hierarchies, e.g. the small relational Grzegorczyk classes. In contrast to a complexity class, a subrecursive class is defined as the least class containing some initial functions and closed under certain composition and recursion schemes. Some of the schemes might contain explicit bounds, but no machine models are involved.

The two hierarchies are induced by neat and natural fragments of a calculus based on finite types and Godel's T, and all the classes in the hierarchies are uniformly defined without referring to explicit bounds. Thus, one should not expect the hierarchies to capture such a wide variety of classes, that is, both time classes, space classes and subrecursive classes. This indicates that a further investigation of the hierarchies might be rewarding, and perhaps shed light upon some of the notoriously hard open problems involving the classes captured by the hierarchies, e.g. maybe some of these problems turn out to be related in some unexpected way.

I aim at a fairly non-technical talk, and I will survey the research that led up to the hierarchies.

Scientific host: Neil Jones. Administrative host: Camilla Jensen. All are welcome.
The Copenhagen Programming Language Seminar (COPLAS) is a collaboration between DIKU, ITU and KVL.
COPLAS is sponsored by FIRST Graduate School.
To receive information about COPLAS talks by email, send a message to prog-lang-request@mail.it-c.dk with the word 'subscribe' as subject or in the body.

For more information about COPLAS, see http://www.coplas.org