In de complexiteitstheorie is PSPACE een complexiteitsklasse die alle beslissingsproblemen bevat die met polynomiale ruimte opgelost kunnen worden. PSPACE kan gedefinieerd worden in termen van DSPACE: .

PSPACE is onder andere gelijk aan de complexiteitsklassen AP, NPSPACE en IP. Het bewijs voor de laatstgenoemde equivalentie, IP = PSPACE, werd geleverd door Adi Shamir. De complexiteitsklasse IP is gedefinieerd met behulp van interactieve bewijssystemen.

In juli 2009 werd bewezen dat PSPACE gelijk is aan QIP. Enkele deelverzamelingen van PSPACE zijn P en NP.

Externe links 
  PSPACE, Complexity Zoo

Complexiteitsklasse