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.
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 :
- {\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)}
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 {\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))}
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 {\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)}
Bibliographie
[modifier | modifier le code ]- (en) Sanjeev Arora et Boaz Barak, Computational Complexity: A Modern Approach, Cambridge University Press, , 579 p. (ISBN 978-0-521-42426-4, lire en ligne). Ouvrage utilisé pour la rédaction de l'article
- Sylvain Perifel, Complexité algorithmique, Éditions Ellipses, , 432 p. (ISBN 978-2-729-88692-9, lire en ligne). Ouvrage utilisé pour la rédaction de l'article
| Classes de complexité (liste) |
|
||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Théorèmes et outils |
|
||||||||||||
| Approches non-standard | |||||||||||||