EXPTIME
aus Wikipedia, der freien Enzyklopädie
In der Komplexitätstheorie steht EXPTIME (manchmal auch nur EXP) für die Komplexitätsklasse der Entscheidungsprobleme, die von einer deterministischen Turingmaschine in durch O(2p(n)) beschränkter Zeit entschieden 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 P eine echte Teilmenge von EXPTIME ist, muss mindestens eine der obigen Teilmengenbeziehungen echt sein.
[Bearbeiten] Weblinks
- EXPTIME im Complexity Zoo (englisch)
