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, $𝖣𝖳𝖨𝖬𝖤(f(n))$ est la classe des problèmes de décision qui, pour une entrée de taille $n$, peuvent être résolus en temps $𝒪(f(n))$ 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 :

$𝖯=\bigcup _{k\in \mathbb{N}}𝖣𝖳𝖨𝖬𝖤(n^k)$

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

$𝖤𝖷𝖯𝖳𝖨𝖬𝖤=\bigcup _{k\in \mathbb{N}}𝖣𝖳𝖨𝖬𝖤\left(2^{n^k}\right)$

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 $f$ et $g$ telles que $f\log f=o(g)$ et $g$ est constructible en temps, l'inclusion stricte suivante est vérifiée :

$𝖣𝖳𝖨𝖬𝖤(f(n))⊊𝖣𝖳𝖨𝖬𝖤(g(n))$

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 $f$ constructible en espace :

$𝖣𝖳𝖨𝖬𝖤(f(n))\subseteq 𝖭𝖳𝖨𝖬𝖤(f(n))\subseteq 𝖣𝖲𝖯𝖠𝖢𝖤(f(n))\subseteq 𝖭𝖲𝖯𝖠𝖢𝖤(f(n))\subseteq 𝖣𝖳𝖨𝖬𝖤\left(2^{𝒪(f(n))}\right)$

Bibliographie

• Modèle:Ouvrage
• Modèle:Ouvrage