Editing EXPSPACE (section)

{{Short description|Set of decision problems}}
In [[computational complexity theory]], '''{{Sans-serif|EXPSPACE}}''' is the [[Set (mathematics)|set]] of all [[decision problem]]s solvable by a deterministic [[Turing machine]] in [[exponential function|exponential]] [[space complexity|space]], 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]], but most authors instead call the resulting class {{Sans-serif|[[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]].

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]] 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.  {{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]]}}, {{Sans-serif|[[NP (complexity)|NP]]}}, and {{Sans-serif|[[P (complexity)|P]]}}. It contains {{Sans-serif|[[EXPTIME]]}} and is believed to strictly contain it, but this is unproven.