EXPSPACE

In <a href="/facts/Computational_complexity_theory/etHuVF3U">computational complexity theory</a>, EXPSPACE is the <a href="/facts/Set_(mathematics)/BfucfHMq">set</a> of all <a href="/facts/Decision_problem/cQNWjbdE">decision problems</a> solvable by a deterministic <a href="/facts/Turing_machine/ojCtglYu">Turing machine</a> in <a href="/facts/Exponential_function/ewlYxvR2">exponential</a> <a href="/facts/Space_complexity/nsnAW5cV">space</a>, i.e., in 
 
 
 
 O
 (
 
 2
 
 p
 (
 n
 )
 
 
 )
 
 
 {\displaystyle O(2^{p(n)})}
 
 space, where 
 
 
 
 p
 (
 n
 )
 
 
 {\displaystyle p(n)}
 
 is a polynomial function of 
 
 
 
 n
 
 
 {\displaystyle n}
 
. Some authors restrict 
 
 
 
 p
 (
 n
 )
 
 
 {\displaystyle p(n)}
 
 to be a <a href="/facts/Linear_function/Ejvy8CKy">linear function</a>, but most authors instead call the resulting class <a href="/facts/ESPACE/4P0DCzVg">ESPACE</a>. If we use a nondeterministic machine instead, we get the class NEXPSPACE, which is equal to EXPSPACE by <a href="/facts/Savitch%27s_theorem/k7SHK3La">Savitch's theorem</a>.
A decision problem is EXPSPACE-complete if it is in EXPSPACE, and every problem in EXPSPACE has a <a href="/facts/Polynomial-time_many-one_reduction/bBvfFxyM">polynomial-time many-one reduction</a> to it. In other words, there is a polynomial-time <a href="/facts/Algorithm/fnl5NmRt">algorithm</a> 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 <a href="/facts/PSPACE/RIkAClvG">PSPACE</a>, <a href="/facts/NP_(complexity)/6muUfVMI">NP</a>, and <a href="/facts/P_(complexity)/2TYvck4k">P</a>. It contains <a href="/facts/EXPTIME/GbTmY8t5">EXPTIME</a> and is believed to strictly contain it, but this is unproven.

EXPSPACE open-in-new

EXPSPACE