thumb|Verbanden tussen complexiteitsklassen. 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, AP, Complexity Zoo NPSPACE NPSPACE, Complexity Zoo en IP. IP, Complexity Zoo 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. PSPACE = QIP, arXiv, Rahul Jain, Zhengfeng Ji, Sarvagya Upadhyay, John Watrous, juli 2009 Enkele deelverzamelingen van PSPACE zijn P en NP.
Externe links PSPACE, Complexity Zoo
Categorie:Complexiteitsklasse