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 
beschränkter Zeit entschieden werden können. 
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 P nach dem Zeithierarchiesatz eine echte Teilmenge von EXPTIME ist, muss mindestens eine der obigen Teilmengenbeziehungen echt sein.
[Bearbeiten] Weblinks
- EXPTIME im Complexity Zoo (englisch)
