Computability in Europe 2006
Logical Approaches to Computational Barriers
|Slot:||Tue, 10:50-11:10, Faraday B (col. 2)|
We describe a natural generalization of ordinary computation to a third-order setting and give a function calculus with nice properties and recursion-theoretic characterizations of several large complexity classes. We then present a number of third-order theories of bounded arithmetic whose definable functions are the classes of the EXP-time hierarchy in the third-order setting.
|websites: Arnold Beckmann||2006-04-29|