In computational complexity theory, ' is the set of all decision problems solvable by a deterministic Turing machine in exponential space, i.e., in O(2^{p(n)}) space, where p(n) is a polynomial function of n. Some authors restrict p(n) to be a linear function, but most authors instead call the resulting class . If we use a nondeterministic machine instead, we get the class , which is equal to by Savitch's theorem.

A decision problem is if it is in , and every problem in has a polynomial-time many-one reduction to it. In other words, there is a polynomial-time algorithm that transforms instances of one to instances of the other with the same answer. problems might be thought of as the hardest problems in .

is a strict superset of , , and . It contains and is believed to strictly contain it, but this is unproven.

Formal definition

In terms of and ,

\mathsf{EXPSPACE} = \bigcup_{k\in\mathbb{N}} \mathsf{DSPACE}\left(2^{n^k}\right) = \bigcup_{k\in\mathbb{N}} \mathsf{NSPACE}\left(2^{n^k}\right)

Examples of problems

Formal languages

An example of an problem is the problem of recognizing whether two regular expressions represent different languages, where the expressions are limited to four operators: union, concatenation, the Kleene star (zero or more copies of an expression), and squaring (two copies of an expression).[1]

Logic

Alur and Henzinger extended linear temporal logic with times (integer) and prove that the validity problem of their logic is EXPSPACE-complete.[2]

Reasoning in the first-order theory of the real numbers with +, ×, = is in EXPSPACE and was conjectured to be EXPSPACE-complete in 1986.[3]

Petri nets

Main article: Petri net

The coverability problem for Petri Nets is -complete.[4]

The reachability problem for Petri nets was known to be -hard for a long time,[5] but shown to be nonelementary,[6] so probably not in . In 2022 it was shown to be Ackermann-complete.[7][8]

It is EXPSPACE-complete to decide whether the reachability of a given vector addition system is finite.[9]

See also

References

  1. ^ Meyer, A.R. 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.
  2. ^ Alur, Rajeev & Henzinger, Thomas A. (1994-01-01). "A Really Temporal Logic". J. ACM. 41 (1): 181–203. doi:10.1145/174644.174651. ISSN 0004-5411
  3. ^ Ben-Or, Michael; Kozen, Dexter; Reif, John (1986-04-01). "The complexity of elementary algebra and geometry". Journal of Computer and System Sciences. 32 (2): 251–264. doi:10.1016/0022-0000(86)90029-2. ISSN 0022-0000
  4. ^ Charles Rackoff (1978). "The covering and boundedness problems for vector addition systems". Theoretical Computer Science
  5. ^ Lipton, R. (1976). "The Reachability Problem Requires Exponential Space". Technical Report 62. Yale University.
  6. ^ Wojciech Czerwiński Sławomir Lasota Ranko S Lazić Jérôme Leroux Filip Mazowiecki (2019). The reachability problem for Petri nets is not elementary. STOC 19.
  7. ^ Leroux, Jerome (February 2022). "The Reachability Problem for Petri Nets is Not Primitive Recursive". 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS). IEEE. pp. 1241–1252. arXiv:2104.12695. doi:10.1109/FOCS52979.2021.00121. ISBN 978-1-6654-2055-6.
  8. ^ Brubaker, Ben (4 December 2023). "An Easy-Sounding Problem Yields Numbers Too Big for Our Universe". Quanta Magazine
  9. ^ Schmitz, Sylvain (2016-02-03). "Complexity Hierarchies beyond Elementary". ACM Transactions on Computation Theory. 8 (1): 1–36. arXiv:1312.5686. doi:10.1145/2858784. ISSN 1942-3454
  • Berman, Leonard (1 May 1980). "The complexity of logical theories". Theoretical Computer Science. 11 (1): 71–77. doi:10.1016/0304-3975(80)90037-7
  • Michael Sipser (1997). Introduction to the Theory of Computation. PWS Publishing. ISBN 0-534-94728-X. Section 9.1.1: Exponential space completeness, pp. 313–317. Demonstrates that determining equivalence of regular expressions with exponentiation is EXPSPACE-complete.