Polynomial-Space

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

See the complexity zoo entry here.

Known relationships

• $\mathbf{IP}=\mathbf{PSPACE}$
• $\mathbf{IP}\ne \mathbf{PSPACE}$ in the random-oracle-model — CCG+94

Participates in

Builds on Polynomial-Space

• PSPACE ⊆ EXP

Produces Polynomial-Space

• BPP ⊆ PSPACE
• coNP ⊆ PSPACE
• IP ⊆ PSPACE
• NP ⊆ PSPACE
• PP ⊆ PSPACE
• QIP = PSPACE