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.
- 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!)