EXPTIME

In der Komplexitätstheorie steht EXPTIME (manchmal auch nur EXP) für die Komplexitätsklasse der Entscheidungsprobleme, die von einer deterministischen Turingmaschine in durch $\mathcal O\left(2^{p(n)}\right)$ beschränkter Zeit entschieden werden können. $p\left(n\right)$ ist dabei ein beliebiges Polynom in der Eingabelänge n. In der DTIME-Notation ausgedrückt gilt also:

$\mbox{EXPTIME} = \bigcup_{k \in \mathbb{N}} \mbox{DTIME}\left(2^{n^k}\right).$

Beziehung zu anderen Komplexitätsklassen

Die folgenden Beziehungen sind bekannt:

NC $\subseteq$ P $\subseteq$ NP $\subseteq$ PSPACE $\subseteq$ EXPTIME $\subseteq$ NEXPTIME

Da P nach dem Zeithierarchiesatz eine echte Teilmenge von EXPTIME ist, muss mindestens eine der obigen Teilmengenbeziehungen echt sein.

Weblinks

• EXPTIME. In: Complexity Zoo. (englisch)