European Summer School on Logic, Language and Information

August 2010, Copenhagen, Denmark

This course is an introduction to Implicit Computational Complexity, which aims at characterizing complexity classes by logical systems and paradigmatic programming languages. After a brief review of computability and complexity, we will describe some proposals for characterizations of the classes of functions computable in polynomial and elementary time. We will focus our attention on functional programming languages and, if time permits, on imperative ones. Interesting connections with mathematical logic (recursion and proof theory) arise along the way.

**A Brief Introduction to Computability and Complexity**

**Functional Programs and Complexity Classes**

**Higher-Order Functions**

**Beyond the Functional Paradigm**

Introduction to to the Course [ pdf | ps ]

Lecture Notes (still in preparation, sorry!)