PSPACE

Uit Wikipedia, de vrije encyclopedie
Naar navigatie springen Jump to search
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,[1] NPSPACE[2] en IP.[3] 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.[4] Enkele deelverzamelingen van PSPACE zijn P en NP.

Externe links[bewerken]