Class Description

NPSPACE: Nondeterministic PSPACE

Equals PSPACE [Sav70].

On the other hand, this result does not relativize if we allow strings of unbounded length to be written to the oracle tape. In particular, there exists an oracle relative to which NPSPACE is not contained in EXP [GTW+91].

Linked From

NSPACE(f(n)): Nondeterministic f(n)-Space

Same as NPSPACE, but with f(n)-space (for some constructible function f) rather than polynomial-space machines.

Contained in DSPACE(f(n)2) [Sav70], and indeed RevSPACE(f(n)2) 95|[CP95].

NSPACE(nk) is strictly contained in NSPACE(nk+ε) for ε>0 [Iba72] (actually the hierarchy theorem is stronger than this, but pretty technical to state).

More about...


PSPACE: Polynomial-Space

The class of decision problems solvable by a Turing machine in polynomial space.

Equals NPSPACE [Sav70], AP [CKS81], and CZK assuming the existence of one-way functions [BGG+90].

Equals IP [Sha90], but PSPACE strictly contains IP with probability 1 [CCG+94].

Contains P#P (P with a #P oracle).

A canonical PSPACE-complete problem is QBF.

Relative to a random oracle, PSPACE strictly contains PH with probability 1 [Cai86].

PSPACE has a complete problem that is both downward self-reducible and random self-reducible [TV02]. It is the largest class with such a complete problem.

Contained in EXP. There exists an oracle relative to which this containment is proper [Dek76].

In descriptive complexity, PSPACE can be defined with 4 differents kind of formulae, FO() which is also FO(PFP) and SO() which is also SO(TC).

More about...