PSPACE

Van Wikipedia, de vrije encyclopedie

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: .

Thumb
Verbanden tussen complexiteitsklassen.

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.

Loading related searches...

Wikiwand - on

Seamless Wikipedia browsing. On steroids.