Jump to content

EXPSPACE

From Wikipedia, the free encyclopedia

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

A decision problem is EXPSPACE-complete if it is in EXPSPACE, and every problem in EXPSPACE 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. EXPSPACE-complete problems might be thought of as the hardest problems in EXPSPACE.

EXPSPACE is a strict superset of PSPACE, NP, and P and is believed to be a strict superset of EXPTIME.

Formal definition

[edit]

In terms of DSPACE and NSPACE,

Examples of problems

[edit]

An example of an EXPSPACE-complete 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]

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

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

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

Relationship to other classes

[edit]

EXPSPACE is known to be a strict superset of PSPACE, NP, and P. It is further suspected to be a strict superset of EXPTIME, however this is not known.

See also

[edit]

References

[edit]
  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. ^ Charles Rackoff (1978). "The covering and boundedness problems for vector addition systems". Theoretical Computer Science: 223–231.
  4. ^ Lipton, R. (1976). "The Reachability Problem Requires Exponential Space". Technical Report 62. Yale University.
  5. ^ 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.
  6. ^ 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.
  7. ^ Brubaker, Ben (4 December 2023). "An Easy-Sounding Problem Yields Numbers Too Big for Our Universe". Quanta Magazine.