EXPSPACE

In complexity theory, EXPSPACE is the set of all decision problems solvable by a deterministic Turing machine in O(2) 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. In terms of DSPACE and NSPACE, A decision proble... more

In complexity theory, EXPSPACE is the set of all decision problems solvable by a deterministic Turing machine in O(2) 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. In terms of DSPACE and NSPACE, A decision problem is EXPSPACE-complete if it is in EXPSPACE, and every problem in 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. EXPSPACE-complete problems might be thought of as the hardest problems in EXPSPACE. EXPSPACE is a strict superset of PSPACE, NP, and P and is believed to be a strict superset of EXPTIME. An example of an EXPSPACE-complete problem is the problem of recognizing whether two regular expressions... less