Seminario Interdipartimentale di Algoritmica  

Monday, June 26, 2006, 12:00 noon Abstract
Implicit Computational Complexity - Some New (and Old) Results
Ugo Dal Lago, Università di Verona

DIS - Department of Computer and System Sciences
Room C3, second floor

Abstract:

We will present some of the logic-based approaches to the characterization of complexity classes, especially polynomial-time. The main feature of these approaches is that complexity classes are described as certain sets of functions, expressed in a framework where there is not an explicit notion of elementary, constant-time, computation step. Of the many ways this could be done, the talk will briefly present two main approaches.

The first one, that could be traced back to Cobham and, later, Bellantoni and Cook, is based on restrictions on primitive recursion. The second one (Leivant, Girard, etc.) defines restrictions to logical systems (like System T, System F or Linear logic) capturing small complexity classes, e.g. by limiting the logical rules responsible for duplication.

This research direction is interesting both from a complexity-theoretic point of view and from a linguistic point view, since techniques developed in implicit complexity enforce resource-aware programming languages.

The talk will focus on some novel results relating fragments of System T and polytime, elementary and primitive recursive functions. These results have been obtained by the speaker in the context of his doctoral studies in Bologna.