Complexité implicite - Wikiwand
For faster navigation, this Iframe is preloading the Wikiwand page for Complexité implicite.

Complexité implicite

Un article de Wikipédia, l'encyclopédie libre.

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, consiste à caractériser les classes de complexité par des restrictions syntaxiques sur le langage de programmation de haut niveau, souvent fonctionnel. Le programme qui résout un problème de la classe est donc écrit à haut niveau, sans référence à une machine de bas niveau, ce qui diffère de la théorie de la complexité classique qui 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, le premier concept issu de cette branche en 1933 est le concept de fonction récursive (qui définit la calculabité par la thèse de Church), puis de fonction récursive primitive[1], équivalent à la réécriture terminant par l'ordre du multi-ensemble des chemins (MPO)[2].

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[3].

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

Notes et références

  1. (hu) Rosza Péter, Recursive Functionen, Budapest, Akademiai Kiado,
  2. (en) D. Hofbauer, « Termination proofs with multiset path orderings imply primitive recursive derivation lengths », Theoretical Computer Science,‎ , p. 129-140
  3. (en) Stephen J. Bellantoni et Stephen Cook, « A new recursion-theoretic characterization of the polytime functions », computational complexity,‎ , p. 97–110 (ISSN 1016-3328, lire en ligne)
  4. (en) Ugo Dal Lago, « Developments in Implicit Complexity (DICE 2012) », Theoretical Computer Science,‎ (lire en ligne)


{{bottomLinkPreText}} {{bottomLinkText}}
Complexité implicite
Listen to this article