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, ${\mathsf {NTIME}}(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 ${\mathcal {O}}(f(n))$ par une machine de Turing non déterministe.

Définitions[modifier | modifier le code]

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 :

{\mathsf {NP}}=\bigcup \limits _{k\in \mathbb {N} }{\mathsf {NTIME}}(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 :

{\mathsf {NEXPTIME}}=\bigcup \limits _{k\in \mathbb {N} }{\mathsf {NTIME}}\left(2^{n^{k}}\right)

Hiérarchie en temps[modifier | modifier le code]

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 :

{\mathsf {NTIME}}(f(n))\subsetneq {\mathsf {NTIME}}(g(n))

Liens avec d'autres classes[modifier | modifier le code]

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 :