EXPSPACE
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 .
≈ 5 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
In computational complexity theory, EXPSPACE is the set of all decision problems solvable by a deterministic Turing machine in exponential space, i.e., in O(2p(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 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. It contains EXPTIME and is believed to strictly contain it, but this is unproven.
Formal definition
edit edit sourceIn terms of DSPACE and NSPACE,
- 𝖤𝖷𝖯𝖲𝖯𝖠𝖢𝖤=⋃k∈ℕ𝖣𝖲𝖯𝖠𝖢𝖤(2nk)=⋃k∈ℕ𝖭𝖲𝖯𝖠𝖢𝖤(2nk)
Examples of problems
edit edit sourceFormal languages
edit edit sourceAn 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]
Logic
edit edit sourceAlur 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
edit edit sourceThe coverability problem for Petri Nets is EXPSPACE-complete.[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 probably not in EXPSPACE. 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
edit edit sourceReferences
edit edit source- ^ 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. Wikipedia revision 1348724056, retrieved 2026-11-18
- ^ 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. Wikipedia revision 1348724056, retrieved 2026-11-18
- ^ 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. Wikipedia revision 1348724056, retrieved 2026-11-18
- ^ Charles Rackoff (1978). "The covering and boundedness problems for vector addition systems". Theoretical Computer Science: 223–231. Wikipedia revision 1348724056, retrieved 2026-11-18
- ^ Lipton, R. (1976). "The Reachability Problem Requires Exponential Space". Technical Report 62. Yale University.
{{cite journal}}: CS1 maint: miscellaneous url (link) Wikipedia revision 1348724056, retrieved 2026-11-18 - ^ 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. Wikipedia revision 1348724056, retrieved 2026-11-18
- ^ 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. Wikipedia revision 1348724056, retrieved 2026-11-18
- ^ Brubaker, Ben (4 December 2023). "An Easy-Sounding Problem Yields Numbers Too Big for Our Universe". Quanta Magazine. Wikipedia revision 1348724056, retrieved 2026-11-18
- ^ 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. Wikipedia revision 1348724056, retrieved 2026-11-18
- 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.
Text derived from https://en.wikipedia.org/w/index.php?oldid=1348724056 under CC BY-SA 4.0; modifications have been made.