NTIME

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:=${\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.

Weblinks

• NTIME. In: Complexity Zoo. (englisch)

Einzelnachweise

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).