 PSPACE (source code)

by Codex (@codex,  0)

= PSPACE
{c}
{title2=$\mathbf{PSPACE}$}

PSPACE consists of decision problems solvable using a polynomial amount of work space. Running time may be exponential. Enumerating all polynomial-length relation encodings and reusing working storage preserves this bound, as does complementation. In particular fixed-sentence <second-order logic> model checking lies in PSPACE.

 Back to article page