"Complexity-theoretic hierarchies"
Author(s): Kristiansen L
Source: LOGICAL APPROACHES TO COMPUTATIONAL BARRIERS, PROCEEDINGS LECTURE NOTES IN COMPUTER SCIENCE 3988: 279-288 2006
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, P, PSPACE, LINSPACE and EXP are captured by the hierarchies. Typical subrecursive classes are also captured, e.g. the small relational Grzegorczyk classes epsilon(0)(*), epsilon(1)(*) and epsilon(2)(*).