Implicit Computational Complexity
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.

Course Program
Teaching Material
Introduction to to the Course [ pdf | ps ]
Lecture Notes (still in preparation, sorry!)