Complexité implicite
# Complexité implicite

En informatique théorique, la complexité implicite est une branche de la théorie de la complexité calculatoire qui caractérise les classes de complexité par des restrictions syntaxiques sur le langage de programmation de haut niveau.

## Définition

La complexité implicite caractérise les classes de complexité par des restrictions syntaxiques sur le langage de programmation de haut niveau, souvent fonctionnel, logique ou par réécriture. Le programme qui résout un problème de la classe est donc écrit sans référence à une machine de bas niveau, alors que la théorie de la complexité classique se réfère à une machine de Turing.

## Techniques

La complexité implicite utilise des techniques de la théorie de la démonstration, des logiques sous-structurelles, de la théorie des modèles, de la théorie de la récursivité, de la réécriture et de la théorie des types.

## Résultats et histoire

Historiquement, les premiers concepts de complexité implicite sont le concept de fonction récursive (qui servira ensuite à définir la calculabilité par la thèse de Church) et le concept de fonction récursive primitive (étudié par Rózsa Péter). La réécriture terminant par l'ordre du multi-ensemble des chemins (MPO) possède une longueur de dérivation dans cette classe.

Le théorème de Bellantoni et Cook montre que les fonctions en temps polynomial (FP) sont définies par la récursion sûre.

Sur base de ce résultat, on a défini la hiérarchie polynomiale et la hiérarchie de comptage.

L'atelier DICE (Developments in Implicit Complexity) est consacré à ce thème.

