# EXPSPACE

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/EXPSPACE
> Markdown URL: https://mediated.wiki/source/EXPSPACE.md
> Source: https://en.wikipedia.org/wiki/EXPSPACE
> Source revision: 1348724056
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

{{Short description|Set of decision problems}}
In [computational complexity theory](/source/computational_complexity_theory), '''{{Sans-serif|EXPSPACE}}''' is the [set](/source/Set_(mathematics)) of all [decision problem](/source/decision_problem)s solvable by a deterministic [Turing machine](/source/Turing_machine) in [exponential](/source/exponential_function) [space](/source/space_complexity), i.e., in <math>O(2^{p(n)})</math> space, where <math>p(n)</math> is a polynomial function of <math>n</math>. Some authors restrict <math>p(n)</math> to be a [linear function](/source/linear_function), but most authors instead call the resulting class {{Sans-serif|[ESPACE](/source/ESPACE)}}. If we use a nondeterministic machine instead, we get the class {{Sans-serif|NEXPSPACE}}, which is equal to {{Sans-serif|EXPSPACE}} by [Savitch's theorem](/source/Savitch's_theorem).

A decision problem is {{Sans-serif|EXPSPACE-complete}} if it is in {{Sans-serif|EXPSPACE}}, and every problem in {{Sans-serif|EXPSPACE}} has a [polynomial-time many-one reduction](/source/polynomial-time_many-one_reduction) to it.  In other words, there is a polynomial-time [algorithm](/source/algorithm) that transforms instances of one to instances of the other with the same answer.  {{Sans-serif|EXPSPACE-complete}} problems might be thought of as the hardest problems in {{Sans-serif|EXPSPACE}}.

{{Sans-serif|EXPSPACE}} is a strict superset of {{Sans-serif|[PSPACE](/source/PSPACE)}}, {{Sans-serif|[NP](/source/NP_(complexity))}}, and {{Sans-serif|[P](/source/P_(complexity))}}. It contains {{Sans-serif|[EXPTIME](/source/EXPTIME)}} and is believed to strictly contain it, but this is unproven.

== Formal definition ==
In terms of {{Sans-serif|[DSPACE](/source/DSPACE)}} and {{Sans-serif|[NSPACE](/source/NSPACE)}},

:<math>\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)</math>

== Examples of problems ==

=== Formal languages ===
An example of an {{Sans-serif|EXPSPACE-complete}} problem is the problem of recognizing whether two [regular expression](/source/regular_expression)s represent different languages, where the expressions are limited to four operators: union, [concatenation](/source/concatenation), the [Kleene star](/source/Kleene_star) (zero or more copies of an expression), and squaring (two copies of an expression).<ref>Meyer, A.R. and [L. Stockmeyer](/source/Larry_Stockmeyer). [https://people.csail.mit.edu/meyer/rsq.pdf The equivalence problem for regular expressions with squaring requires exponential space]. ''13th IEEE Symposium on Switching and Automata Theory'', Oct 1972, pp.125&ndash;129.</ref>

=== Logic ===
Alur and Henzinger extended [linear temporal logic](/source/linear_temporal_logic) with times (integer) and prove that the validity problem of their logic is EXPSPACE-complete.<ref>{{Cite journal|last1=Alur|first1=Rajeev|last2=Henzinger|first2=Thomas A.|date=1994-01-01|title=A Really Temporal Logic|journal=J. ACM|volume=41|issue=1|pages=181–203|doi=10.1145/174644.174651|issn=0004-5411|doi-access=free}}</ref>

Reasoning in the first-order theory of the real numbers with +, ×, = is in EXPSPACE and was conjectured to be EXPSPACE-complete in 1986.<ref>{{Cite journal |last1=Ben-Or |first1=Michael |last2=Kozen |first2=Dexter |last3=Reif |first3=John |date=1986-04-01 |title=The complexity of elementary algebra and geometry |url=https://dx.doi.org/10.1016/0022-0000%2886%2990029-2 |journal=Journal of Computer and System Sciences |volume=32 |issue=2 |pages=251–264 |doi=10.1016/0022-0000(86)90029-2 |issn=0022-0000|url-access=subscription }}</ref>

=== Petri nets ===
{{Main|Petri net}}

The coverability problem for [Petri Nets](/source/Petri_Nets) is {{Sans-serif|EXPSPACE}}-complete.<ref>{{cite journal | 
  author = Charles Rackoff |
  title = The covering and boundedness problems for vector addition systems |
  journal = Theoretical Computer Science |
  pages = 223–231 |
  date = 1978}}</ref>

The [reachability problem](/source/reachability_problem) for Petri nets was known to be {{Sans-serif|EXPSPACE}}-hard for a long time,<ref>{{cite journal | last = Lipton | first = R. | url = http://citeseer.ist.psu.edu/contextsummary/115623/0 | title = The Reachability Problem Requires Exponential Space | journal = Technical Report 62 | publisher = Yale University | date = 1976 }}</ref> but shown to be [nonelementary](/source/Nonelementary_problem),<ref>{{cite conference | author = Wojciech Czerwiński Sławomir Lasota Ranko S Lazić Jérôme Leroux Filip Mazowiecki
| title = The reachability problem for Petri nets is not elementary | book-title = STOC 19 | date = 2019}}</ref> so probably not in {{Sans-serif|EXPSPACE}}. In 2022 it was shown to be [Ackermann](/source/Ackermann_function)-complete.<ref name=":1">{{Cite book |last=Leroux |first=Jerome |chapter=The Reachability Problem for Petri Nets is Not Primitive Recursive |date=February 2022 |title=2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS) |publisher=IEEE |pages=1241–1252 |doi=10.1109/FOCS52979.2021.00121 |isbn=978-1-6654-2055-6|arxiv=2104.12695 }}</ref><ref name=":0">{{Cite web |last=Brubaker |first=Ben |date=4 December 2023 |title=An Easy-Sounding Problem Yields Numbers Too Big for Our Universe |url=https://www.quantamagazine.org/an-easy-sounding-problem-yields-numbers-too-big-for-our-universe-20231204/ |website=[Quanta Magazine](/source/Quanta_Magazine)}}</ref>

It is EXPSPACE-complete to decide whether the reachability of a given [vector addition system](/source/vector_addition_system) is finite.<ref name=":12">{{Cite journal |last=Schmitz|first=Sylvain|date=2016-02-03|title=Complexity Hierarchies beyond Elementary|url=https://dl.acm.org/doi/10.1145/2858784|journal=ACM Transactions on Computation Theory|language=en|volume=8|issue=1|pages=1–36|doi=10.1145/2858784|arxiv=1312.5686|issn=1942-3454}}</ref>

==See also==
*[Game complexity](/source/Game_complexity)

== References ==

<references />
*{{cite journal |last1=Berman |first1=Leonard |title=The complexity of logical theories |journal=Theoretical Computer Science |date=1 May 1980 |volume=11 |issue=1 |pages=71–77 |doi=10.1016/0304-3975(80)90037-7|doi-access=free }}
* {{cite book | author = Michael Sipser | year = 1997 | title = Introduction to the Theory of Computation | publisher = PWS Publishing | isbn = 0-534-94728-X | url-access = registration | url = https://archive.org/details/introductiontoth00sips | author-link = Michael Sipser }} Section 9.1.1: Exponential space completeness, pp.&nbsp;313&ndash;317. Demonstrates that determining equivalence of regular expressions with exponentiation is EXPSPACE-complete.

{{ComplexityClasses}}

Category:Complexity classes

---
Adapted from the Wikipedia article [EXPSPACE](https://en.wikipedia.org/wiki/EXPSPACE) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/EXPSPACE?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.