EXPSPACE

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

In terms of DSPACE and NSPACE,

Examples of problems

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]

If the Kleene star is left out, then that problem becomes NEXPTIME-complete, which is like EXPTIME-complete, except it is defined in terms of non-deterministic Turing machines rather than deterministic.

It has also been shown by L. Berman in 1980 that the problem of verifying/falsifying any first-order statement about real numbers that involves only addition and comparison (but no multiplication) is in EXPSPACE.

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][4] The reachability problem for Petri nets was known to be EXPSPACE-hard for a long time,[5] but shown to be nonelementary,[6] so it is probably not in EXPSPACE.

Relationship to other classes

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

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. Lipton, R. (1976). "The Reachability Problem Requires Exponential Space". Technical Report 62. Yale University.
  4. Charles Rackoff (1978). "The covering and boundedness problems for vector addition systems". Theoretical Computer Science: 223–231.
  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.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.