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

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

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.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. The authors of the article are listed here. Additional terms may apply for the media files, click on images to show image meta data.

[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.