Computability in Europe 2006
Logical Approaches to Computational Barriers

Print current page  Print this page

Regular Talk:
Complexity-Theoretic Hierarchies

Speaker: Lars Kristiansen
Slot: Mon, 11:10-11:30, Faraday B (col. 2)

Abstract

We introduce two  hierarchies of unknown ordinal height.
The  hierarchies are induced by  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.  Deterministic complexity classes like $\logspace$, $\classp$,
$\pspace$, $\linspace$ and $\exptime$ are captured by the hierarchies.
Typical subrecursive classes are also captured, e.g.\
the small relational Grzegorczyk classes $\calE^0_*$, $\calE^1_*$
and  $\calE^2_*$. 


websites: Arnold Beckmann 2006-04-19 Valid HTML 4.01! Valid CSS! eXTReMe Tracker hit counters by www.free-counters.net