Reinhard Kahle (Universidade Nova de Lisboa), Computational Complexity and Applicative Theories (joint work with Isabel Oitavem).


  • Jan. 30, 2012, 16:30 - 17:00


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.