In computational complexity theory, PSPACE is the set of all decision problems which can be solved by a Turing machine using a polynomial amount of space.
If we denote by SPACE(t(n)), the set of all problems that can be solved by Turing machines using at most t(n) space for some function t of the input size n, then we can define PSPACE formally as
PSPACE is a strict superset of the set of context-sensitive languages.
It turns out that allowing th...
more
In computational complexity theory, PSPACE is the set of all decision problems which can be solved by a Turing machine using a polynomial amount of space.
If we denote by SPACE(t(n)), the set of all problems that can be solved by Turing machines using at most t(n) space for some function t of the input size n, then we can define PSPACE formally as
PSPACE is a strict superset of the set of context-sensitive languages.
It turns out that allowing the Turing machine to be nondeterministic does not add any extra power. Because of Savitch's theorem, NPSPACE is equivalent to PSPACE, essentially because a deterministic Turing machine can simulate a nondeterministic Turing machine without needing much more space (even though it may use much more time).
The following relations are known between PSPACE and the complexity classes NL, P, NP, PH, EXPTIME and EXPSPACE:
It is known that, in the first and second line, at least one of the set containments must be strict, but it is not known which. It...
less
