PSPACE

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken
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: \cup_{k=1}^{\infty} \text{DSPACE}(n^k).

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]

Bronnen, noten en/of referenties
  1. (en) AP, Complexity Zoo
  2. (en) NPSPACE, Complexity Zoo
  3. (en) IP, Complexity Zoo
  4. (en) PSPACE = QIP, arXiv, Rahul Jain, Zhengfeng Ji, Sarvagya Upadhyay, John Watrous, juli 2009