WikiDer > PSPACE

Beziehungen zwischen Komplexitätsklassen.

In dem Komplexitätstheorie ist PSPACE ein Komplexitätsklasse diese alle Entscheidungsprobleme enthält die mit Polynom Raum gelöst werden kann. PSPACE kann definiert werden in DSPACE: ${displaystyle cup _{k=1}^{infty }{ ext{DSPACE}}(n^{k})}$.

PSPACE ist unter anderem gleich den Komplexitätsklassen AP,^[1]NPSPACE^[2] und IP.^[3] Der Beweis für die letztere Äquivalenz, IP = PSPACE, wurde zur Verfügung gestellt von Adi Shamir. Die Komplexitätsklasse IP wird definiert mit interaktive Beweissysteme.

Im Juli 2009 wurde bewiesen, dass PSPACE gleich ist mit QIP.^[4] Ein paar Teilmengen von PSPACE sein p und NP.

Externe Links

• (und) PSPACE, Komplexität Zoo