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