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[1]. In vorheriger Quelle wird auch gezeigt, dass diese Klasse mit NTIME(n) zusammenfällt.)
NP:= $\bigcup _{k=0}^{\infty }$ NTIME(n^k)
NE:=NTIME(2^O(n))
NEXP:= $\bigcup _{k=0}^{\infty }$ NTIME(2^{n^k})

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

Ronald V. Book, Sheila A. Greibach: Quasi-realtime languages (Extended Abstract). ACM, S. 15–18. doi:10.1145/800169.805416

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. The authors of the article are listed here. Additional terms may apply for the media files, click on images to show image meta data.

[1] Ronald V. Book, Sheila A. Greibach: Quasi-realtime languages (Extended Abstract). ACM, S. 15–18. doi:10.1145/800169.805416