Loading AI tools
Van Wikipedia, de vrije encyclopedie
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.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
