NEXPTIME

In der Komplexitätstheorie steht NEXPTIME (manchmal auch nur NEXP) für die Komplexitätsklasse der Entscheidungsprobleme, die von einer nichtdeterministischen Turingmaschine in durch O($2^{p(n)}$) beschränkter Zeit akzeptiert werden können. $p(n)$ ist dabei 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

Die folgenden Beziehungen sind bekannt:

NC ⊆ P ⊆ NP ⊆ PSPACE ⊆ EXPTIME ⊆ 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

• NEXPTIME. In: Complexity Zoo. (englisch)