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 ${\displaystyle {\mathcal {O}}(2^{p(n)})}$ (siehe Landau-Notation) beschränkter Zeit akzeptiert werden können. Hierbei ist ${\displaystyle p(n)}$ ein beliebiges Polynom von der Eingabelänge ${\displaystyle n}$. In der DTIME-Notation ausgedrückt gilt also:

${\displaystyle {\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.

Vollständigkeit

Es gibt NEXPTIME-vollständige Probleme. Ein Beispiel ist das Problem festzustellen, ob zwei gegebene reguläre Ausdrücke die gleiche Sprache erzeugen, wobei die Ausdrücke nur die Operatoren Vereinigung, Verkettung, und Verdopplung enthalten.^[1] In den üblichen Notationen regulärer Ausdrücke wären also nur

• Vereinigung: (x|y), erkennt x oder y,
• Verkettung: xy, erkennt x und dann y, und
• Dopplung: x{2}, erkennt x genau zweimal,

erlaubt, wobei x und y bereits nach diesem Schema korrekt gebildete Ausdrücke oder Literale aus dem gegebenen Alphabet sind. Die Zeichen (, |, ) und {2} werden als nicht Teil des Literal-Alphabets aufgefasst. Die Dopplung ist nur ein Symbol mehr, wohingegen das Verketten von x mit sich selbst die Größe der Eingabe maßgeblich erhöht.

Weblinks

• NEXPTIME. In: Complexity Zoo. (englisch)

Einzelnachweise

1. ↑ Meyer, A.R. and L. Stockmeyer. The equivalence problem for regular expressions with squaring requires exponential space. 13th IEEE Symposium on Switching and Automata Theory, Oct 1972, S. 125–129.