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}$ — Sha90; the ⊆ direction is folklore (ip-to-pspace-ccg-94)
• $\mathbf{IP}\ne \mathbf{PSPACE}$ in the random-oracle-model — CCG+94

Participates in

Builds on Polynomial-Space

• PSPACE ⊆ EXP
• PSPACE ⊆ IP

Produces Polynomial-Space

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