Plus précisément, est la classe des problèmes de décision qui, pour une entrée de taille , peuvent être résolus en temps 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 :
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 :
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 et telles que et est croissante et constructible en temps, l'inclusion stricte suivante est vérifiée :
Les classes NTIME sont reliées aux classes de complexité en temps déterministe DTIME et aux classes de complexité en espaceDSPACE et NSPACE par les inclusions suivantes, pour toute fonction constructible en espace :