EXPSPACE

In complexity theory , EXPSPACE (Exponential Space) stands for the complexity class of decision problems that can be decided by a deterministic Turing machine in terms of space , where any polynomial is. If one considers non-deterministic Turing machines, one obtains the class NEXPSPACE . According to Savitch's theorem , EXPSPACE = NEXPSPACE. ${\displaystyle {\mathcal {O}}\left(2^{p(n)}\right)}$ ${\displaystyle p(n)}$

Expressed in the DSPACE / NSPACE notation, the following applies:

${\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).}$

Relationship to other complexity classes

The following relationships are known:

NP PSPACE = NPSPACE EXPTIME NEXPTIME EXPSPACE = NEXPSPACE ${\displaystyle \subseteq }$ ${\displaystyle \subseteq }$ ${\displaystyle \subseteq }$ ${\displaystyle \subseteq }$

and also PSPACE EXPSPACE ${\displaystyle \subset }$

completeness

There are EXPSPACE-complete problems. One example is the problem of determining whether two given regular expressions produce the same language, where the expressions contain only the operators union, concatenation, Kleenian envelope, and doubling. In the usual notations of regular expressions, there would only be

• Association :, recognize or ,(x|y)xy
• Concatenation:, xyrecognizes xand then y,
• Kleenesche covering:, x*recognizes xas often as desired, possibly not at all, and
• Doubling:, x{2}detects xexactly twice,

allowed, where xand yare already under this scheme properly formed expressions or literals from the given alphabet. The characters (, |, ), *and {2}are seen as not part of the literal alphabet. The doubling is just one more symbol, whereas the concatenation of xwith itself increases the size of the input significantly.

The same question without a clover shell represents a NEXPTIME-complete problem.

literature

• Christos H. Papadimitriou : Computational Complexity . Addison-Wesley, Reading / Mass, 1995, ISBN 978-0-201-53082-7 , 20.1 And Beyond ... (English).

Web links

• EXPSPACE . In: Complexity Zoo. (English)

Individual evidence

1. ↑ Meyer, AR and L. Stockmeyer . The equivalence problem for regular expressions with squaring requires exponential space . 13th IEEE Symposium on Switching and Automata Theory , Oct 1972, pp. 125-129.