NTIME

In d​er Komplexitätstheorie s​teht NTIME(f) für d​ie Menge d​er Sprachen, d​ie von e​iner nichtdeterministischen Turingmaschine i​n Zeit O(f) akzeptiert werden können.

Mittels NTIME werden u​nter 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 s​ich zeigen, d​ass die Teilmengenbeziehung i​n der Hierarchie Q NP NE NEXP echt sind.

  • NTIME. In: Complexity Zoo. (englisch)

Einzelnachweise

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