---
title: EXPSPACE
slug: expspace
qid: 
snapshot: enwiki-001348724056
content_hash: 
license: CC BY-SA 4.0
source: https://en.wikipedia.org/w/index.php?oldid=1348724056
tags: [130042203, 23057298, 23118434, 23603337]
---

# EXPSPACE

> [!note] Provenance
> Snapshot `enwiki-001348724056` · content root `…`
> Derived from <https://en.wikipedia.org/w/index.php?oldid=1348724056> · Licensed CC BY-SA 4.0

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.

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. \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) Reasoning in the first-order theory of the real numbers with +, ×, = is in EXPSPACE and was conjectured to be EXPSPACE-complete in 1986. ==See also== Game complexity
