PSPACE Complexity Class

complexity-theory

Definition

PSPACE Complexity Class

The complexity class PSPACE contains all decision problems that can be solved by a deterministic Turing machine using a polynomial amount of space on the work tape.

• Space usage: $\mathcal{O}(|I{|}^k)$ for some constant $k$

In other words, the machine may take exponential time, but it must reuse only polynomial space.

$$\mathrm{P}\subseteq \mathrm{PSPACE}$$

Idea

• PSPACE is a very large class and contains many difficult problems.
• “Polynomial space” means that the amount of memory grows only polynomially with the input size.
• The input itself may be much larger than the available work space, so the machine must process it without copying it completely.
• PSPACE-complete problems are regarded as intractable unless $\mathrm{P}=\mathrm{PSPACE}$.

Examples

TTT-winning-strategy

Let $n,k\in \mathbb{N}$, and let $C$ be a game position on an $n\times n$ board for the generalised $(n,k)$-Tic-Tac-Toe game.

The decision problem asks whether Player 1 has a winning strategy from position $C$.

This problem is in PSPACE because the game lasts at most $n^2$ moves, so the search depth is polynomial in the input size, and a depth-first exploration of the game tree uses only polynomial space.