Accueil🇫🇷Chercher

DTIME

En théorie de la complexité, DTIME (ou TIME) désigne une famille de classes de complexité caractérisée par leur complexité en temps sur une machine de Turing déterministe.

Plus précisément, est la classe des problèmes de décision qui, pour une entrée de taille , peuvent être résolus en temps par une machine de Turing déterministe.

Définitions

La classe P des problèmes de décision décidables par une machine de Turing déterministe en temps polynomial par rapport à la taille de l'entrée peut être définie comme :

De même, la classe EXPTIME des problèmes de décision décidable en temps exponentiel est définie comme :

Hiérarchie en temps

Informellement, le théorème de hiérarchie en temps déterministe indique que disposer de plus de temps permet de décider davantage de problèmes. Plus précisément, pour toutes fonctions et telles que et est constructible en temps, l'inclusion stricte suivante est vérifiée :

Liens avec d'autres classes

Les classes DTIME sont reliées aux classes de complexité en espace DSPACE et NSPACE par les inclusions suivantes, pour toute fonction constructible en espace :

Bibliographie

Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.