imported>SchlurcherBot: Bot: http → https

2025-07-09T00:52:50Z

Bot: http → https

Neue Seite

In der [[Komplexitätstheorie]] bezeichnet '''PSPACE''' die [[Komplexitätsklasse|Klasse]] der [[Entscheidbar|Entscheidungsprobleme]], die von [[Determinismus|deterministischen]] [[Turingmaschine]]n mit [[Polynom|polynomiellem]] [[Platzkomplexität|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 [[Nichtdeterministische Turingmaschine|nichtdeterministischen Turingmaschine]] entscheidbaren Probleme.

Für die Komplexitätsklasse '''IP''', die alle Entscheidungsprobleme enthält, die ein [[interaktives Beweissystem]] besitzen, gilt: IP = PSPACE.<ref name="Sha90" />

Auch für die Klasse '''AP''' der durch [[alternierende Turingmaschine]]n in polynomieller Zeit erkannten Sprachen gilt AP = PSPACE.<ref name="AB100" />

Falls [[Einwegfunktion]]en existieren, gilt für die Klasse '''CZK''' der Sprachen, für die (computational) [[Zero-Knowledge-Beweis]]e existieren, ebenfalls CZK = IP = PSPACE.<ref name="BBG88" />

== Probleme in PSPACE ==
Es existieren viele Probleme in PSPACE, auf die sich alle anderen PSPACE-Probleme in [[Polynomialzeitreduktion|Polynomialzeit reduzieren]] lassen. Von diesen so genannten PSPACE-[[Vollständigkeit (Komplexitätstheorie)|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 [[Kontextsensitive Grammatik|kontextsensitiven Grammatik]] erzeugt werden kann.

== Beziehung zu anderen Komplexitätsklassen ==

[[Datei:Complexity subsets pspace.svg|mini|Zusammenhang mit anderen Komplexitätsklassen]]

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

:[[NC (Komplexitätsklasse)|NC]] <math>\subseteq</math> [[P (Komplexitätsklasse)|P]] <math>\subseteq</math> [[NP (Komplexitätsklasse)|NP]] <math>\subseteq</math> PSPACE
:[[NC (Komplexitätsklasse)|NC]] <math>\subset</math> PSPACE

Es wird vermutet, dass alle der obigen [[Mengenlehre|Inklusionen]] echt sind:

:[[NC (Komplexitätsklasse)|NC]] <math>\subset</math> [[P (Komplexitätsklasse)|P]] <math>\subset</math> [[NP (Komplexitätsklasse)|NP]] <math>\subset</math> PSPACE

Die Inklusion [[NP (Komplexitätsklasse)|NP]] <math>\subseteq</math> 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 [[Erfüllbarkeitsproblem der Aussagenlogik|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 ==
<references>
<ref name="AB100">{{Literatur
| Autor= Sanjeev Arora and Boaz Barak
| Titel=Computational Complexity: A Modern Approach
| Verlag=Cambridge University Press
| Jahr=2009
| Seiten=100
| ISBN=978-0-521-42426-4
| Online=https://www.cs.princeton.edu/theory/complexity/
}}</ref>
<ref name="BBG88">{{Literatur
| Autor=[[Michael Ben-Or]], [[Oded Goldreich]], [[Shafi Goldwasser]], [[Johan Håstad]], [[Joe Kilian]], [[Silvio Micali]], [[Phillip Rogaway]]
| Titel=Everything Provable is Provable in Zero-Knowledge
| Sammelwerk=CRYPTO’ 88
| Reihe=LNCS
| Band=403
| Verlag=Springer
| Jahr=1990
| Seiten=37–56
| DOI=10.1007/0-387-34799-2_4
}}</ref>
<ref name="Sha90">{{Literatur
| Autor=Adi Shamir
| Titel=IP=PSPACE
| Sammelwerk=Proceedings of IEEE FOCS'90
| Verlag=IEEE
| Jahr=1990
| Seiten=11–15
| DOI=10.1109/FSCS.1990.89519
}}</ref>
</references>

== Weblinks ==
* {{Complexity Zoo|PSPACE|P#pspace}}

[[Kategorie:Komplexitätsklasse]]
[[Kategorie:Abkürzung]]

PSPACE - Versionsgeschichte

imported>SchlurcherBot: Bot: http → https