Théorème de hiérarchie en temps déterministe

Un article de Wikipédia, l'encyclopédie libre.
Sauter à la navigation Sauter à la recherche

Le théorème de hiérarchie en temps déterministe est un énoncé de la théorie de la complexité, un domaine de l'informatique théorique. Informellement le théorème dit qu'avec plus de temps une machine déterministe peut résoudre plus des tâches. C'est l'un des théorèmes de hiérarchie en temps (en).

Contexte[modifier | modifier le code]

Le théorème parle en particulier de machines de Turing déterministes. On note DTIME(f(n)), l'ensemble des problèmes de décision qui peuvent être décidés par une telle machine avec une complexité en temps O(f(n)), où n est la taille de l'entrée.

Énoncé[modifier | modifier le code]

Le théorème de hiérarchie en temps déterministe est le suivant[1] :

Théorème — Soit f et g des fonctions des entiers naturels dans les entiers naturels, telles que f(n) est différent de 0 (pour tout n), g est constructible en temps et f.log(f)= o(g). Alors DTIME(f(n)) ⊊ DTIME(g(n)).

Preuve[modifier | modifier le code]

Théorème proches[modifier | modifier le code]

Il existe d'autres théorèmes de hiérarchie. Par exemple, il existe d'autres théorèmes de hiérarchie en temps (en) pour les machines non-déterministes. Il existe aussi des théorème pour la complexité en espace[2].

Histoire[modifier | modifier le code]

Le théorème de hiérarchie en temps déterministe est dû à Richard E. Stearns et Juris Hartmanis en 1965[3]. Le résultat a été amélioré par F. C. Hennie et Richard E. Stearns en améliorant l'efficacité de la machine de Turing universelle[4].

Notes et références[modifier | modifier le code]

  1. Sylvain Perifel, Complexité algorithmique, Ellipses, , 432 p. (ISBN 9782729886929, lire en ligne), chap. 2 (« Considérations de base sur le temps »), p. 35-38.
  2. Sylvain Perifel, Complexité algorithmique, Ellipses, , 432 p. (ISBN 9782729886929, lire en ligne).
  3. Juris Hartmanis et Richard E. Stearns, « On the computational complexity of algorithms », Transactions of the American Mathematical Society, American Mathematical Society, vol. 117,‎ , p. 285-306 (ISSN 0002-9947, DOI 10.2307/1994208, JSTOR 1994208, Math Reviews 0170805).
  4. F. C. Hennie et Richard E. Stearns, « Two-Tape Simulation of Multitape Turing Machines », J. ACM, New York, NY, USA, ACM, vol. 13, no 4,‎ , p. 533-546 (ISSN 0004-5411, DOI 10.1145/321356.321362)