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, ${\displaystyle {\mathsf {NTIME}}(f(n))}$ est la classe des problèmes de décision qui, pour une entrée de taille ${\displaystyle n}$, peuvent être résolus en temps ${\displaystyle {\mathcal {O}}(f(n))}$ par une machine de Turing non déterministe.

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 :

${\displaystyle {\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 :

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

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

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

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 ${\displaystyle f}$ constructible en espace :

${\displaystyle {\mathsf {DTIME}}(f(n))\subseteq {\mathsf {NTIME}}(f(n))\subseteq {\mathsf {DSPACE}}(f(n))\subseteq {\mathsf {NSPACE}}(f(n))\subseteq {\mathsf {DTIME}}\left(2^{{\mathcal {O}}(f(n))}\right)}$

• (en) Sanjeev Arora et Boaz Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 20 avril 2009, 579 p. (ISBN 978-0-521-42426-4, lire en ligne). 
• Sylvain Perifel, Complexité algorithmique, Éditions Ellipses, 22 avril 2014, 432 p. (ISBN 978-2-729-88692-9, lire en ligne). 

• Portail de l'informatique théorique