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:= NTIME(nk)
  • NE:=NTIME(2O(n))
  • NEXP:= NTIME(2nk)

Mittels Diagonalisierung lässt sich zeigen, dass die Teilmengenbeziehung in der Hierarchie QNPNENEXP echt sind.

Bearbeiten
  • NTIME. In: Complexity Zoo. (englisch)

Einzelnachweise

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