EXPSPACE

In computational complexity theory, the complexity class EXPSPACE is the set of decision problems that can be solved with a deterministic Turing machine in space O(2^p(n)), where p(n) is a polynomial function over n . According to Savitch's Theorem, this class is the same as that considered by non-deterministic Turing machines. When constraining p(n) as a linear function, the resulting class is called ESPACE.

In DSPACE terms,

EXPSPACE= k한 한 NDSPACE(2nk){displaystyle {mbox{EXPSPACE}}=bigcup _{kin mathbb {N}}}{mbox{DSPACE}}(2^{n^{k}}}})}

The complexity class EXPSPACE-complete is the class of problems that are in EXPSPACE such that every problem in EXPSPACE has a polynomial transformation to every problem in EXPSPACE-complete. In other words, there is an algorithm that works in polynomial time that transforms the instances of one problem into the instances of another with the same answer. The EXPSPACE-complete set can be seen as the set of the most difficult EXPSPACE problems.

EXPSPACE strictly contains the PSPACE, NP-complete, NP, and P classes and is believed to strictly contain the EXPTIME set as well.

An example of a problem in EXPSPACE-complete is deciding whether two regular expressions represent different languages, when the regular operators used are union, concatenation, Kleene closure (zero or more copies of an expression), and the square (two copies of an expression).

If the Kleene closure is not included, the problem is NEXPTIME-complete, which is like EXPTIME-complete, except that it is defined according to non-deterministic Turing machines.

In 1980, L. Berman showed that the problem of checking or falsifying any first-order expression over real numbers that only uses addition and comparison (but not multiplication) is in EXPSPACE.