In der Komplexitätstheorie steht NTIME(f) für die Menge der Sprachen, die von einer nichtdeterministischen Turingmaschine in Zeit O(f) akzeptiert werden können.

Mittels NTIME werden unter anderem folgende Komplexitätsklassen definiert bzw. charakterisiert:

• Q=NTIME(n) (Formal wird Q als Familie aller Sprachen L mit L=L(M) definiert, wobei jede Berechnung von M auf Eingabe w höchstens |w| Schritte benötigt^[1]. In vorheriger Quelle wird auch gezeigt, dass diese Klasse mit NTIME(n) zusammenfällt.)
• NP:=${\displaystyle \bigcup _{k=0}^{\infty }}$ NTIME(n^k)
• NE:=NTIME(2^O(n))
• NEXP:=${\displaystyle \bigcup _{k=0}^{\infty }}$ NTIME(2^nk)

Mittels Diagonalisierung lässt sich zeigen, dass die Teilmengenbeziehung in der Hierarchie Q ⊂ NP ⊂ NE ⊂ NEXP echt sind.

• NTIME. In: Complexity Zoo. (englisch)

1. ↑ Ronald V. Book, Sheila A. Greibach: Quasi-realtime languages (Extended Abstract). 1st Annual ACM Symposium on Theory of Computing. In: Proceedings of the 1st Annual ACM Symposium on Theory of Computing, May 5-7, 1969, Marina del Rey, CA, USA. ACM, 1969, S. 15–18, doi:10.1145/800169.805416 (englisch).