computer science//complexity theory//PSPACE

PSPACE is the class of decision problems solvable by a Turing machine using polynomial space: the workspace is bounded, but the computation time may be exponential.

PSPACE is the class of decision problems solvable by a Turing machine using polynomial space: the workspace is bounded, but the computation time may be exponential.

It contains P, NP and co-NP. Whether P equals PSPACE is open, though widely believed false.

PSPACE equals NPSPACE (Savitch's theorem, 1970), so nondeterminism does not help when the constraint is space, only when it is time.

The PSPACE-complete problems include quantified Boolean formulas (QBF), many two-player games (generalized chess, Go on arbitrary boards) and planning problems with constraints.

The analogy between PSPACE and chain-of-thought reasoning (extended thinking), with the context window as bounded scratch space and the thinking tokens as steps, each composing a new transformation (compositionality), is imperfect: transformers are not Turing machines, and the context window is not true random-access memory.