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. In vorheriger Quelle wird auch gezeigt, dass diese Klasse mit NTIME(n) zusammenfällt.) NP:= NTIME(nk) NE:=NTIME(2O(n)) NEXP:= NTIME(2nk)
Mittels Diagonalisierung lässt sich zeigen, dass die Teilmengenbeziehung in der Hierarchie Q ⊂ NP ⊂ NE ⊂ NEXP echt sind.
Weblinks
Einzelnachweise
Kategorie:Komplexitätsklasse Kategorie:Abkürzung