NTIME

Einfache Sprache

Def. NTIME

Sei $t:\mathbb N\to \mathbb R^+$ ein Funktion. Die nichtdeterministische Zeitkomplexitätsklasse

$$\mathbf{NTIME}(t(n))$$

ist definiert als die Menge aller Sprachen, die von einer Nichtdeterministische Turingmaschine mit Laufzeit Big O $O(t(n))$ entscheidbar sind.