PSPACE

 related topics {math, number, function} {rate, high, increase}

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.

Contents

Formal definition

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

$\mbox{PSPACE} = \bigcup_{k\in\mathbb{N}} \mbox{SPACE}(n^k)$

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).

Relation among other classes

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 is widely suspected that all are strict.

In contrast, the containments in the third line are both known to be strict. The first follows from direct diagonalization (the space hierarchy theorem, $\mbox{NL} \subsetneq \mbox{NPSPACE}$) and the fact that PSPACE = NPSPACE via Savitch's theorem. The second follows simply from the space hierarchy theorem.

The hardest problems in PSPACE are the PSPACE-Complete problems. See PSPACE-Complete for examples of problems that are suspected to be in PSPACE but not in NP.

Other characterizations

An alternative characterization of PSPACE is the set of problems decidable by an alternating Turing machine in polynomial time, sometimes called APTIME or just AP.

A logical characterization of PSPACE from descriptive complexity theory is that it is the set of problems expressible in second-order logic with the addition of a transitive closure operator. A full transitive closure is not needed; a commutative transitive closure and even weaker forms suffice. It is the addition of this operator that (possibly) distinguishes PSPACE from PH.