In der Komplexitätstheorie steht NEXPTIME (manchmal auch nur NEXP) für die Komplexitätsklasse der Entscheidungsprobleme, die von einer nichtdeterministischen Turingmaschine in durch (siehe Landau-Notation) beschränkter Zeit akzeptiert werden können. Hierbei ist ein beliebiges Polynom von der Eingabelänge . In der DTIME-Notation ausgedrückt gilt also:
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.A. R. Meyer, 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. 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
Einzelnachweise
Kategorie:Komplexitätsklasse