EXPSPACE

In complexity theory is EXPSPACE ( Exponential Space) for the complexity class of decision problems that can be decided by a deterministic Turing machine in space by, where is an arbitrary polynomial. Looking at non- determinisitsche Turing machines yields the class NEXPSPACE. By the Theorem of Savitch applies EXPSPACE = NEXPSPACE.

Expressed in the DSPACE / NSPACE notation applies:

Relation to other complexity classes

The following relations are known:

And further PSPACE EXPSPACE