NTIME (Komplexitätsklasse)

Sei $f:\mathbb{N}\to \mathbb{N}$ eine Funktion. Die Klasse NTIME(f(n)) ist die Menge aller Sprachen $L$, die von einer nichtdeterministischen Turingmaschine (NTM) akzeptiert werden, deren Berechnungspfade für jede Eingabe der Länge $n$ maximal die Länge $O(f(n))$ haben.