Logical Approaches to Computational Barriers

Complexity-Theoretic Hierarchies

Speaker:
| Lars Kristiansen |

Slot: |
Array, 11:10-11:30, col. 2 |

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 |