Surf Wiki
Save to docs
general/complexity-classes

From Surf Wiki (app.surf) — the open knowledge base

EXPSPACE

Set of decision problems

Set of decision problems

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).

Logic

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

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

Petri nets

Main article: Petri net

The coverability problem for Petri Nets is -complete.{{cite journal | author = Charles Rackoff | title = The covering and boundedness problems for vector addition systems | journal = Theoretical Computer Science | pages = 223–231 | date = 1978}}

The reachability problem for Petri nets was known to be -hard for a long time, but shown to be nonelementary,{{cite conference | author = Wojciech Czerwiński Sławomir Lasota Ranko S Lazić Jérôme Leroux Filip Mazowiecki

References

  • Section 9.1.1: Exponential space completeness, pp. 313–317. Demonstrates that determining equivalence of regular expressions with exponentiation is EXPSPACE-complete.

References

  1. Meyer, A.R. and [[Larry Stockmeyer. L. 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–129.
  2. (1994-01-01). "A Really Temporal Logic". J. ACM.
  3. (1986-04-01). "The complexity of elementary algebra and geometry". Journal of Computer and System Sciences.
  4. Lipton, R.. (1976). "The Reachability Problem Requires Exponential Space". Yale University.
  5. Leroux, Jerome. (February 2022). "2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS)". IEEE.
  6. Brubaker, Ben. (4 December 2023). "An Easy-Sounding Problem Yields Numbers Too Big for Our Universe".
Info: Wikipedia Source

This article was imported from Wikipedia and is available under the Creative Commons Attribution-ShareAlike 4.0 License. Content has been adapted to SurfDoc format. Original contributors can be found on the article history page.

complexity-classes
Want to explore this topic further?

Ask Mako anything about EXPSPACE — get instant answers, deeper analysis, and related topics.

Research with Mako

Free with your Surf account

Content sourced from Wikipedia, available under CC BY-SA 4.0.

This content may have been generated or modified by AI. CloudSurf Software LLC is not responsible for the accuracy, completeness, or reliability of AI-generated content. Always verify important information from primary sources.

Report