NEXPTIME

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

In der Komplexitätstheorie steht NEXPTIME (manchmal auch nur NEXP) für die Komplexitätsklasse der Entscheidungsprobleme, die von einer nichtdeterministischen Turingmaschine in durch \mathcal{O}(2^{p(n)}) (siehe Landau-Notation) beschränkter Zeit akzeptiert werden können. Hierbei ist p(n) ein beliebiges Polynom von der Eingabelänge n. In der DTIME-Notation ausgedrückt gilt also:

\mbox{NEXPTIME} = \bigcup_{k\in\mathbb{N}} \mbox{NTIME}\left(2^{n^k}\right).

Beziehung zu anderen Komplexitätsklassen[Bearbeiten]

Die folgenden Beziehungen sind bekannt:

NCPNPPSPACEEXPTIME ⊆ NEXPTIME

Da nach dem Zeithierarchiesatz gilt, dass NP eine echte Teilmenge von NEXPTIME ist, und NC eine echte Teilmenge von PSPACE ist, muss mindestens eine der obigen Teilmengenbeziehungen echt sein.

Weblinks[Bearbeiten]

  • NEXPTIME. In: Complexity Zoo. (englisch)