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.

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^[1] (étudié par Rózsa Péter^[2]). La réécriture terminant par l'ordre du multi-ensemble des chemins (MPO)^[3] 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^[4].

Sur base de ce résultat, on a défini la hiérarchie polynomiale^[5] et la hiérarchie de comptage^[6].

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

Notes et références

↑ Hilbert, David, « Logic-Kalkül », Reprinted and translated in ' David Hilbert's Lectures on the Foundations of Arithmetic and Logic',‎ 1920 (DOI 10.1007/978-3-540-69444-1_2)
↑ (hu) Rosza Péter, Recursive Functionen, Budapest, Akademiai Kiado, 1951
↑ (en) D. Hofbauer, « Termination proofs with multiset path orderings imply primitive recursive derivation lengths », Theoretical Computer Science,‎ 1992, p. 129-140
↑ (en) Stephen J. Bellantoni et Stephen Cook, « A new recursion-theoretic characterization of the polytime functions », computational complexity,‎ juin 1992, p. 97–110 (ISSN 1016-3328, lire en ligne)
↑ (en) Isabel Oitavem, « The polynomial hierarchy of functions and its levels », Theoretical Computer Science,‎ 2022, p. 25-34 (DOI 10.1016/j.tcs.2021.11.016)
↑ (en) Ugo Dal Lago, Reinhard Kahle et Isabel Oitavem, « Implicit recursion-theoretic characterizations of counting classes », Arch. Math. Log. 61(7-8),‎ 2022, p. 1129-1144
↑ (en) Ugo Dal Lago, « Developments in Implicit Complexity (DICE 2012) », Theoretical Computer Science,‎ 20 juin 2015 (lire en ligne)

v · m

Théorie de la complexité (informatique théorique)

Classes de complexité
(liste)

Classes classiques	L NL P NP NP-complet co-NP co-NP-complet NP-facile PSPACE E EXPTIME NE NEXPTIME EXPSPACE
Classes randomisées et quantiques	RP ZPP BPP EQP BQP QMA IP Protocole Arthur-Merlin PP BPL RL
Autres	P/poly NC APX AC⁰ UP
Classes de fonctions calculables	#-P #-P-complet
Hiérarchies	Hiérarchie polynomiale PH Hiérarchie booléenne
Familles de classes	DTIME NTIME DSPACE NSPACE

Théorèmes et outils

Théorèmes structurels	Théorème de Savitch Théorème d'Immerman-Szelepcsényi Théorème PCP Théorème de Karp-Lipton Théorème de Sipser-Gács-Lautemann Théorème de Toda
Outils et réductions	Théorème d'accélération linéaire Théorème de Cook Réduction polynomiale Kernelisation

Approches non-standard

Complexité descriptive
Complexité implicite

Portail de l'informatique théorique

Related Articles