Reinhard Kahle (Universidade Nova de Lisboa), Computational Complexity and Applicative Theories (joint work with Isabel Oitavem).
Schedule
- Jan. 30, 2012, 16:30 - 17:00
Abstract
By work of Strahm and Cantini, it was already shown that Applicative Theories -
the rst order part of Feferman's system of Explicit Mathematics - provide a very
handy formal framework to characterize classes of computational complexity. In
this talk, we present an applicative theory for FPH and its levels. The presenta-
tion will also include some general consideration concerning the set-up of induction
principles corresponding to recursion principles for complexity classes.
By work of Strahm and Cantini, it was already shown that Applicative Theories - the rst order part of Feferman's system of Explicit Mathematics - provide a very handy formal framework to characterize classes of computational complexity. In this talk, we present an applicative theory for FPH and its levels. The presenta- tion will also include some general consideration concerning the set-up of induction principles corresponding to recursion principles for complexity classes.