NEXPTIME
aus Wikipedia, der freien Enzyklopädie
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(2p(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:
[Bearbeiten] Beziehung zu anderen Komplexitätsklassen
Die folgenden Beziehungen sind bekannt:
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.
[Bearbeiten] Weblinks
- NEXPTIME im Complexity Zoo (englisch)
