imported>YMS: Sprache

2024-04-18T22:00:03Z

Sprache

Neue Seite

In der [[Komplexitätstheorie]] steht '''NEXPTIME''' (manchmal auch nur '''NEXP''') für die [[Komplexitätsklasse]] der [[Entscheidbar|Entscheidungsprobleme]], die von einer [[Nichtdeterministische Turingmaschine|nichtdeterministischen Turingmaschine]] in durch <math>\mathcal{O}(2^{p(n)})</math> (siehe [[Landau-Notation]]) beschränkter [[Zeitkomplexität|Zeit]] akzeptiert werden können. Hierbei ist <math>p(n)</math> ein beliebiges [[Polynom]] von der Eingabelänge <math>n</math>. In der [[DTIME]]-Notation ausgedrückt gilt also:
:<math>\mbox{NEXPTIME} = \bigcup_{k\in\mathbb{N}} \mbox{NTIME}\left(2^{n^k}\right).</math>

== Beziehung zu anderen Komplexitätsklassen ==
Die folgenden Beziehungen sind bekannt:
:[[NC (Komplexitätsklasse)|NC]] ⊆ [[P (Komplexitätsklasse)|P]] ⊆ [[NP (Komplexitätsklasse)|NP]] ⊆ [[PSPACE]] ⊆ [[EXPTIME]] ⊆ NEXPTIME
Da nach dem [[Komplexitätstheorie#Zeithierarchiesatz|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 [[Regulärer Ausdruck#Semantik|Operatoren]] Vereinigung, Verkettung, und Verdopplung enthalten.<ref>A. R. Meyer, [[Larry Stockmeyer|L. Stockmeyer]]: [http://people.csail.mit.edu/meyer/rsq.pdf The equivalence problem for regular expressions with squaring requires exponential space]. ''13th IEEE Symposium on Switching and Automata Theory'', Oct 1972, S. 125–129.</ref> In den üblichen Notationen regulärer Ausdrücke wären also nur
* Vereinigung: <code>(''x''|''y'')</code>, erkennt <code>''x''</code> oder <code>''y''</code>,
* Verkettung: <code>''xy''</code>, erkennt <code>''x''</code> und dann <code>''y''</code>, und
* Dopplung: <code>''x''{2}</code>, erkennt <code>''x''</code> genau zweimal,
erlaubt, wobei <code>''x''</code> und <code>''y''</code> bereits nach diesem Schema korrekt gebildete Ausdrücke oder Literale aus dem gegebenen Alphabet sind. Die Zeichen <code>(</code>, <code>|</code>, <code>)</code> und <code>{2}</code> werden als nicht Teil des Literal-Alphabets aufgefasst.
Die Dopplung ist nur ein Symbol mehr, wohingegen das Verketten von <code>''x''</code> mit sich selbst die Größe der Eingabe maßgeblich erhöht.

== Weblinks ==
* {{Complexity Zoo|NEXPTIME|N#nexp}}

== Einzelnachweise ==
<references />

[[Kategorie:Komplexitätsklasse]]

NEXPTIME - Versionsgeschichte

imported>YMS: Sprache