PSPACE

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: ∪ k = 1 ∞ DSPACE ( n k ) {\displaystyle \cup _{k=1}^{\infty }{\text{DSPACE}}(n^{k})} . 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.

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: ∪ k = 1 ∞ DSPACE ( n k ) {\displaystyle \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 | brontekst bewerken]

• (en) PSPACE, Complexity Zoo

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