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 de tâches. C'est l'un des .
Contexte Le théorème parle en particulier de machines de Turing déterministes. On note DTIME(f) 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é Le théorème de hiérarchie en temps déterministe est le suivant., en donne deux démonstrations. :
Théorème proches Il existe d'autres . Par exemple, il existe d'autres théorèmes de hiérarchie en temps pour les machines non déterministes. Il existe aussi des théorèmes pour la complexité en espace..
Histoire Le théorème de hiérarchie en temps déterministe est dû à Richard E. Stearns et Juris Hartmanis en 1965.. 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..
Notes et références
Hiérarchie en temps déterministe