EXPSPACE

In der Komplexitätstheorie steht EXPSPACE (Exponential Space) für die Komplexitätsklasse der Entscheidungsprobleme, die von einer deterministischen Turingmaschine in durch ${\displaystyle {\mathcal {O}}\left(2^{p(n)}\right)}$ Platz entschieden werden können, wobei ${\displaystyle p(n)}$ ein beliebiges Polynom ist. Betrachtet man nicht-deterministische Turingmaschinen, so erhält man die Klasse NEXPSPACE. Nach dem Satz von Savitch gilt EXPSPACE = NEXPSPACE.

In der DSPACE / NSPACE-Notation ausgedrückt gilt also:

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