Logical Approaches to Computational Barriers

Third-Order Computation and Bounded Arithmetic

Speaker:
| Alan Skelley |

Author(s): |
Alan Skelley |

Slot: |
Array, 10:50-11:10, 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 |