EXPTIME

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

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