In der rechenbetonten Kompliziertheitstheorie ist PSPACE der Satz aller Entscheidungsprobleme, die durch eine Maschine von Turing mit einer polynomischen verfügbaren Fläche gelöst werden können.

Formelle Definition

Wenn wir durch, der Satz aller Probleme anzeigen, die durch das Maschinenverwenden von Turing am grössten Teil des Raums für etwas Funktion der Eingangsgröße gelöst werden können, dann können wir PSPACE formell als definieren

PSPACE ist eine strenge Obermenge des Satzes von mit dem Zusammenhang empfindlichen Sprachen.

Es stellt sich heraus, dass das Erlauben die Maschine von Turing, nichtdeterministisch zu sein, keine Extramacht hinzufügt. Wegen des Lehrsatzes von Savitch ist NPSPACE zu PSPACE im Wesentlichen gleichwertig, weil eine deterministische Maschine von Turing eine nichtdeterministische Maschine von Turing vortäuschen kann, ohne viel mehr Raum zu brauchen (wenn auch es viel mehr Zeit verwenden kann). Außerdem sind die Ergänzungen aller Probleme in PSPACE auch in PSPACE, diesen Co-PSPACE = PSPACE bedeutend.

Beziehung unter anderen Klassen

Die folgenden Beziehungen sind zwischen PSPACE und den Kompliziertheitsklassen NL, P, NP, PH bekannt, EXPTIME und EXPSPACE (bemerken Sie, dass das ist nicht):

:::

Es ist bekannt, dass in der ersten und zweiten Linie mindestens eine der Satz-Eindämmungen streng sein müssen, aber es ist der nicht bekannt. Es wird weit vermutet, dass alle streng sind.

Wie man

beide bekannt, sind die Eindämmungen in der dritten Linie streng. Das erste folgt aus direktem diagonalization (der Raumhierarchie-Lehrsatz,) und die Tatsache das über den Lehrsatz von Savitch. Das zweite folgt einfach vom Raumhierarchie-Lehrsatz.

Die härtesten Probleme in PSPACE sind die PSPACE-ganzen Probleme. Sieh PSPACE-abgeschlossen für Beispiele von Problemen, die, wie man verdächtigt, in PSPACE, aber nicht in NP sind.

Andere Charakterisierungen

Eine alternative Charakterisierung von PSPACE ist der Satz von Problemen, die durch eine Wechselmaschine von Turing in der polynomischen Zeit manchmal entscheidbar sind, genannt APTIME oder gerade AP.

Eine logische Charakterisierung von PSPACE aus der beschreibenden Kompliziertheitstheorie besteht darin, dass es der Satz von Problemen expressible in der Logik der zweiten Ordnung mit der Hinzufügung eines transitiven Verschluss-Maschinenbedieners ist. Ein voller transitiver Verschluss ist nicht erforderlich; ein transitiver Ersatzverschluss und noch schwächere Formen genügen. Es ist die Hinzufügung dieses Maschinenbedieners, der (vielleicht) PSPACE vom PH unterscheidet.

Ein Hauptergebnis der Kompliziertheitstheorie besteht darin, dass PSPACE als alle Sprachen charakterisiert werden kann, die durch ein besonderes interaktives Probesystem, dasjenige erkennbar sind, das die Klasse IP definiert. In diesem System gibt es einen allmächtigen prover, der versucht, einen randomized polynomisch-maligen verifier zu überzeugen, dass eine Schnur auf der Sprache ist. Es sollte im Stande sein, den verifier mit der hohen Wahrscheinlichkeit zu überzeugen, wenn die Schnur auf der Sprache ist, aber nicht im Stande sein sollte, sie außer mit der niedrigen Wahrscheinlichkeit zu überzeugen, wenn die Schnur nicht auf der Sprache ist.

PSPACE kann als die Quant-Kompliziertheitsklasse QIP charakterisiert werden.

PSPACE-Vollständigkeit

Eine Sprache B ist PSPACE-abgeschlossen, wenn es in PSPACE ist und es PSPACE-hart ist, was für ganzen Einen PSPACE, Einen B bedeutet, wo Ein B bedeutet, dass es die polynomisch-malige eine Verminderung von bis B gibt. PSPACE-ganze Probleme sind zum Studieren von PSPACE Problemen von großer Bedeutung, weil sie die schwierigsten Probleme in PSPACE vertreten. Die Entdeckung einer einfachen Lösung eines PSPACE-ganzen Problems würde bedeuten, dass wir eine einfache Lösung aller anderen Probleme in PSPACE haben, weil alle PSPACE Probleme auf ein PSPACE-ganzes Problem reduziert werden konnten.

• Abschnitt 8.2-8.3 (Die Klasse PSPACE, PSPACE-Vollständigkeit), Seiten 281-294.

• Kapitel 19: Polynomischer Raum, Seiten 455-490.

• Kapitel 8: Raumkompliziertheit

Links

• Vortrag gleitet auf der Raumkompliziertheit Von der Universität Torontos
• Vortrag gleitet auf der Raumkompliziertheit Von der Universität von Princeton