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 O( $2 p (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:

$\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 ⊆ P ⊆ NP ⊆ PSPACE ⊆ EXPTIME ⊆ NEXPTIME

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

BPP | BQP | E | EXPTIME | L | NC | NL | NP | P | PSPACE | #P