PSPACE

In der Komplexitätstheorie bezeichnet PSPACE die Klasse der Entscheidungsprobleme, die von deterministischen Turingmaschinen mit polynomiellem Platz entschieden werden können.

Alternative Charakterisierungen

Nach dem Satz von Savitch ist PSPACE gleich der Klasse NPSPACE, der Klasse der auf polynomiellem Platz von einer nichtdeterministischen Turingmaschine entscheidbaren Probleme.

Für die Komplexitätsklasse IP, die alle Entscheidungsprobleme enthält, die ein interaktives Beweissystem besitzen, gilt: IP = PSPACE.[1]

Auch für die Klasse AP der durch alternierende Turingmaschinen in polynomieller Zeit erkannten Sprachen gilt AP = PSPACE.[2]

Falls Einwegfunktionen existieren, gilt für die Klasse CZK der Sprachen, für die (computational) Zero-Knowledge-Beweise existieren, ebenfalls CZK = IP = PSPACE.[3]

Probleme in PSPACE

Es existieren viele Probleme in PSPACE, auf die sich alle anderen PSPACE-Probleme in Polynomialzeit reduzieren lassen. Von diesen so genannten PSPACE-vollständigen Problemen wird angenommen, dass sie nicht in NP liegen.

Das kanonische PSPACE-vollständige Problem ist das Erfüllbarkeitsproblem für quantifizierte boolesche Formeln.

Ein weiteres PSPACE-vollständiges Problem ist die Entscheidung, ob ein gegebenes Wort von einer gegebenen kontextsensitiven Grammatik erzeugt werden kann.

Beziehung zu anderen Komplexitätsklassen

Zusammenhang mit anderen Komplexitätsklassen

Das Verhältnis zu anderen bekannten Komplexitätsklassen ist wie folgt:

NC ${\displaystyle \subseteq }$ P ${\displaystyle \subseteq }$ NP ${\displaystyle \subseteq }$ PSPACE

NC ${\displaystyle \subset }$ PSPACE

Es wird vermutet, dass alle der obigen Inklusionen echt sind:

NC ${\displaystyle \subset }$ P ${\displaystyle \subset }$ NP ${\displaystyle \subset }$ PSPACE

Die Inklusion NP ${\displaystyle \subseteq }$ PSPACE ergibt sich daraus, dass lediglich für ein beliebiges NP-schweres Problem gezeigt werden muss, dass es in PSPACE liegt. Dies ist zum Beispiel für SAT der Fall: es gibt zwar exponentiell viele Belegungen für die Variablen, aber jede einzelne dieser Belegungen kann in polynomiellem Platz abgespeichert werden. Somit können sämtliche Belegungen nacheinander aufgezählt und ausprobiert werden, wodurch SAT beantwortet werden kann, und somit auch sämtliche weiteren Probleme in NP.

Einzelnachweise

1. Adi Shamir: IP=PSPACE. In: Proceedings of IEEE FOCS'90. IEEE, 1990, S. 11–15, doi:10.1109/FSCS.1990.89519. 
2. Sanjeev Arora and Boaz Barak: Computational Complexity: A Modern Approach. Cambridge University Press, 2009, ISBN 978-0-521-42426-4, S. 100 (princeton.edu). 
3. Michael Ben-Or, Oded Goldreich, Shafi Goldwasser, Johan Håstad, Joe Kilian, Silvio Micali, Phillip Rogaway: Everything Provable is Provable in Zero-Knowledge. In: CRYPTO’ 88 (= LNCS). Band 403. Springer, 1990, S. 37–56, doi:10.1007/0-387-34799-2_4. 

Weblinks

• PSPACE. In: Complexity Zoo. (englisch)