Page "EXPSPACE" Paragraph 0

In complexity theory, EXPSPACE is the set of all decision problems solvable by a deterministic Turing machine in O ( 2 < sup > p ( n )</ sup >) 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 ESPACE.

) If we use a nondeterministic machine instead, we get the class NEXPSPACE, which is equal to EXPSPACE by Savitch's theorem.