NTIME

En théorie de la complexité, NTIME désigne une famille de classes de complexité caractérisée par leur complexité en temps sur une machine de Turing non 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 non déterministe.

Définitions

La classe NP des problèmes de décision décidables par une machine de Turing non 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 NEXPTIME des problèmes de décision décidable par une machine de Turing non déterministe 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 non 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(n+1)=o(g(n))$ et $g$ est croissante et constructible en temps, l'inclusion stricte suivante est vérifiée :

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

Liens avec d'autres classes

Les classes NTIME sont reliées aux classes de complexité en temps déterministe DTIME et 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