NTIME

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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:

  • Q:=NTIME(n)
  • 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.

Weblinks[Bearbeiten | Quelltext bearbeiten]

  • NTIME. In: Complexity Zoo. (englisch)