Editing Complexity class (section)

====EXPSPACE and NEXPSPACE====
{{Main article|EXPSPACE}}
The complexity classes '''EXPSPACE''' and '''NEXPSPACE''' are the space analogues to '''[[EXPTIME]]''' and '''[[NEXPTIME]]'''. That is, '''EXPSPACE''' is the class of problems solvable in exponential space by a deterministic Turing machine and '''NEXPSPACE''' is the class of problems solvable in exponential space by a nondeterministic Turing machine. Or more formally,
:<math>\mathsf{EXPSPACE} = \bigcup_{k\in\mathbb{N}} \mathsf{DSPACE}(2^{n^k})</math>
:<math>\mathsf{NEXPSPACE} = \bigcup_{k\in\mathbb{N}} \mathsf{NSPACE}(2^{n^k})</math>

[[Savitch's theorem]] showed that '''EXPSPACE'''='''NEXPSPACE'''. This class is extremely broad: it is known to be a strict superset of '''PSPACE''', '''NP''', and '''P''', and is believed to be a strict superset of '''EXPTIME'''.