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.
In computational complexity theory, EXPSPACE is the set of all decision problems solvable by a deterministic Turing machine in exponential space, i.e....
to each other in the following way: L⊆NL⊆P⊆NP⊆PSPACE⊆EXPTIME⊆NEXPTIME⊆EXPSPACE (where ⊆ denotes the subset relation). However, many relationships are...
complexity classes in the following way: P ⊆ NP ⊆ PSPACE ⊆ EXPTIME ⊆ NEXPTIME ⊆ EXPSPACE. Furthermore, by the time hierarchy theorem and the space hierarchy theorem...
the set of decision problems that can be solved by a deterministic Turing machine in space 2O(n). See also EXPSPACE. Complexity Zoo: Class ESPACE v t e...
needed to represent the problem. It turns out that PSPACE = NPSPACE and EXPSPACE = NEXPSPACE by Savitch's theorem. Other important complexity classes include...
currently stands, it might be PSPACE-complete, EXPTIME-complete, or even EXPSPACE-complete. Japanese ko rules state that only the basic ko, that is, a move...
and Jonsson have demonstrated that the problem of conformant planning is EXPSPACE-complete, and 2EXPTIME-complete when the initial situation is uncertain...
alternating Turing machine in exponential space, and is a superset of EXPSPACE. An example of a problem in 2-EXPTIME that is not in EXPTIME is the problem...
reachability problem for Petri nets, MELL entailment must be at least EXPSPACE-hard, although decidability itself has had the status of a longstanding...
determine when it is safe to stop. In fact, this problem was shown to be EXPSPACE-hard years before it was shown to be decidable at all (Mayr, 1981). Papers...
planning are decidable, with known complexities ranging from NP-complete to 2-EXPSPACE-complete, and some HTN problems can be efficiently compiled into PDDL,...
problem (EXPSPACE problems) on von Neumann machines, it still grows exponentially with the size of the problem on DNA machines. For very large EXPSPACE problems...
Solvable with exponential space with linear exponent EXP Same as EXPTIME EXPSPACE Solvable with exponential space EXPTIME Solvable in exponential time FNP...
{\displaystyle \bigcup _{k\in \mathbb {N} }{\mathsf {NSPACE}}(n^{k})} EXPSPACE = NEXPSPACE = ⋃ k ∈ N N S P A C E ( 2 n k ) {\displaystyle \bigcup _{k\in...
proved the theorems ALOGSPACE = P AP = PSPACE APSPACE = EXPTIME AEXPTIME = EXPSPACE A S P A C E ( f ( n ) ) = ⋃ c > 0 D T I M E ( 2 c f ( n ) ) = D T I M E...
time classes P, EXPTIME, 2-EXPTIME,... and the space classes L, PSPACE, EXPSPACE,...; as well as the classes of the hierarchy DTIME(O(n)), DSPACE(O(n))...
constantly many alternations. E ⊆ NE ⊆ EH⊆ ESPACE, EXP ⊆ NEXP ⊆ EXPH⊆ EXPSPACE, EH ⊆ EXPH. Sarah Mocas, Separating classes in the exponential-time hierarchy...
{\displaystyle \bigcup _{k\in \mathbb {N} }{\mathsf {DSPACE}}(n^{k})} EXPSPACE = ⋃ k ∈ N D S P A C E ( 2 n k ) {\displaystyle \bigcup _{k\in \mathbb {N}...
exponential nondeterministic time (2-NEXP) and double exponential space (2-EXPSPACE). Completeness is under polynomial time many-to-one reductions. (Also,...
NPSPACE, and using Savitch's theorem to show that PSPACE = NPSPACE. PSPACE ⊊ EXPSPACE. This last corollary shows the existence of decidable problems that are...
a Petri net is decidable. Since 1976, it is known that this problem is EXPSPACE-hard. There are results on how much to implement this problem in practice...
is undecidable for bounded MSC-graphs and that safe-realizability is in EXPSPACE, along with other interesting results related to the verification of MSC-graphs...
Global Information
