Lesson plan
Implicit computational complexity
Implicit computational complexity (ICC) is a subfield of computational complexity theory that characterizes programs by constraints on the way in which they are constructed, without reference to a specific underlying machine model or to explicit bounds on computational resources unlike conventional complexity theory. The central goal of ICC is to identify programming formalisms — such as restricted formal languages, type systems, or recursion schemes — whose expressive power coincides exactly with a given complexity class, so that membership in the class becomes a consequence of syntactic well-formedness rather than a separate computational argument. ICC was developed in the 1990s and employs the techniques of proof theory, substructural logic, linear logic, model theory and recursion theory to prove bounds on the expressive power of high-level formal languages. Among its founding contributions are Girard, Scedrov, and Scott’s bounded linear logic (1992), Bellantoni and Cook’s function algebra based on predicative recursion (1992), and Jones’s cons-free programming language characterisation of polynomial time (1999). ICC is also concerned with the practical realization of functional programming languages, language tools and type theory that can control the resource usage of programs in a formally verifiable sense.…
Article summary
Implicit computational complexity (ICC) is a subfield of computational complexity theory that characterizes programs by constraints on the way in which they are constructed, without reference to a specific underlying machine model or to explicit bounds on computational resources unlike conventional complexity theory. The central goal of ICC is to identify programming formalisms — such as restricted formal languages, type systems, or recursion schemes — whose expressive power coincides exactly with a given complexity class, so that membership in the class becomes a consequence of syntactic well-formedness rather than a separate computational argument. ICC was developed in the 1990s and employs the techniques of proof theory, substructural logic, linear logic, model theory and recursion theory to prove bounds on the expressive power of high-level formal languages. Among its founding contributions are Girard, Scedrov, and Scott’s bounded linear logic (1992), Bellantoni and Cook’s function algebra based on predicative recursion (1992), and Jones’s cons-free programming language characterisation of polynomial time (1999). ICC is also concerned with the practical realization of functional programming languages, language tools and type theory that can control the resource usage of programs in a formally verifiable sense.…
Key claims
No claims recorded.
Discussion questions
- Summarise the article in your own words. Which single claim would you verify first, and why?
- Which claim in this article is most likely to be revised as the sources update? How would you check its current status?
- If two sources disagreed about one of these facts, what would you need in order to trust one over the other?
Bibliography
No sources recorded.
Key claims and bibliography are generated from the same tracked claims and sources as the article page.