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:=\bigcup_{k=0}^\infty NTIME(nk)
  • NE:=NTIME(2O(n))
  • NEXP:=\bigcup_{k=0}^\infty NTIME(2nk)

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

Weblinks[Bearbeiten]

  • NTIME. In: Complexity Zoo. (englisch)