In der Kompliziertheitstheorie ist ein Entscheidungsproblem PSPACE-abgeschlossen, wenn es in der Kompliziertheitsklasse PSPACE ist, und jedes Problem in PSPACE darauf in der polynomischen Zeit reduziert werden kann (sieh abgeschlossen (Kompliziertheit)). Von den Problemen, die PSPACE-abgeschlossen sind, kann als die härtesten Probleme in PSPACE gedacht werden, weil eine Lösung irgendwelchen solchen Problems leicht verwendet werden konnte, um jedes andere Problem in PSPACE zu beheben. Wie man weit verdächtigt, sind diese Probleme außerhalb der berühmteren Kompliziertheitsklassen P und NP, aber das ist nicht bekannt. Es ist bekannt, dass sie außerhalb der kleinen Klasse NC liegen, da NC in PolyL = DSPACE enthalten wird ((loggen Sie n))), der in PSPACE durch den Raumhierarchie-Lehrsatz ausschließlich enthalten wird.

Diskussion

Das erste bekannte PSPACE-ganze Problem war das Wortproblem für deterministische mit dem Zusammenhang empfindliche Grammatiken. Im Wortproblem für mit dem Zusammenhang empfindliche Grammatiken werden man eine Reihe grammatischer Transformationen gegeben, die zunehmen können, aber, die Länge eines Satzes nicht abnehmen können, und bestimmen möchten, ob ein gegebener Satz durch diese Transformationen erzeugt werden konnte. Die technische Bedingung "des Determinismus" (Andeutung grob, dass jede Transformation es offensichtlich macht, dass es verwendet wurde) stellt sicher, dass dieser Prozess im polynomischen Raum und S.-Y gelöst werden kann. Die 1964 Arbeit von Kuroda "Klassen von Sprachen und geradlinig begrenzten Automaten" hat gezeigt, dass irgendwelcher (vielleicht nichtdeterministisch) im geradlinigen Raum berechenbares Programm in die Syntaxanalyse einer mit dem Zusammenhang empfindlichen Grammatik in einem Weg umgewandelt werden konnte, der Determinismus bewahrt.

1970 hat der Lehrsatz von Savitch gezeigt, dass PSPACE unter dem Nichtdeterminismus geschlossen wird, andeutend, dass sogar nichtdeterministische mit dem Zusammenhang empfindliche Grammatiken in PSPACE sind.

Aber das archetypische PSPACE-ganze Problem wird allgemein genommen, um das gemessene Formel-Problem von Boolean zu sein (gewöhnlich abgekürzt zu QBF oder TQBF; der T tritt "wahr" ein), eine Generalisation des ersten bekannten NP-complete Problems, das (GESESSENE) Problem von Boolean satisfiability. Das satisfiability Problem ist das Problem dessen, ob es Anweisungen von Wahrheitswerten zu Variablen gibt, die einen Ausdruck von Boolean wahr machen. Zum Beispiel würde ein Beispiel von GESESSENEN die Frage dessen sein, ob der folgende wahr ist:

:

Das gemessene Formel-Problem von Boolean unterscheidet sich im Erlauben sowohl universale als auch existenzielle Quantifizierung über die Werte der Variablen:

:.

Der Beweis, dass QBF ein PSPACE-ganzes Problem ist, ist im Wesentlichen eine Neuformulierung des Beweises des Lehrsatzes von Savitch auf der Sprache der Logik, und ist ein bisschen mehr technisch.

Bemerken Sie, dass das NP-complete Problem einem typischen Rätsel ähnelt: Dort ist ein Weg, Werte einzustecken, der behebt das Problem? Das PSPACE-ganze Problem ähnelt einem Spiel: Gibt es eine Bewegung, die ich, solch machen kann, dass für alle Bewegungen mein Gegner machen könnte, wird es dann eine Bewegung geben, die ich machen kann, um zu gewinnen? Die Frage lässt existenziellen und universalen quantifiers abwechseln. Nicht überraschend erweisen sich viele Rätsel, NP-complete zu sein, und viele Spiele erweisen sich, PSPACE-abgeschlossen zu sein.

Beispiele von Spielen, die PSPACE-abgeschlossen sind (wenn verallgemeinert, so dass sie auf einem n &times gespielt werden können; n Ausschuss) sind die Spielhexe und Reversi und die Solitär-Spielstoßzeit, Mahjong, Atomix und Sokoban. Einige andere verallgemeinerte Spiele, wie Schach, Kontrolleure (Ziehen), und Gehen sind EXPTIME-abgeschlossen, weil ein Spiel zwischen zwei vollkommenen Spielern sehr lang sein kann, so werden sie kaum in PSPACE sein. Aber sie werden PSPACE-abgeschlossen werden, wenn ein Polynom zur Zahl von Bewegungen gebunden hat, wird beachtet.

Bemerken Sie, dass die Definition der PSPACE-Vollständigkeit auf der asymptotischen Kompliziertheit basiert: Die Zeit, die man braucht, um ein Problem der Größe n, in der Grenze als n zu beheben, wächst ohne bestimmten. Das bedeutet ein Spiel wie Kontrolleure (der auf 8 &times gespielt wird; 8 Ausschuss) konnte nie PSPACE-abgeschlossen sein (tatsächlich, sie können in der unveränderlichen Zeit und Raum mit einer sehr großen Nachschlagetabelle gelöst werden). Deshalb wurden alle Spiele durch das Spielen von ihnen auf einem n &times modifiziert; n Ausschuss stattdessen; in einigen Fällen, solcher bezüglich des Schachs, sind diese Erweiterungen etwas künstlich und subjektiv.

Beispiele von PSPACE-ganzen Problemen

Folgender ist einige PSPACE-ganze Probleme mit Umrissen der Algorithmen zeigend, dass sie in PSPACE sind. Mehr Beispiele können an der Liste von PSPACE-ganzen Problemen gefunden werden.

TQBF

• Lassen Sie TQBF = {

• Wenn F keinen quantifier hat, bewerten Sie und akzeptieren Sie, dass iff F wahr ist.
• Wenn F=pF', rekursiv F' [p=1] und F' [p=0] bewerten Sie, iff akzeptieren Sie, den beide akzeptieren.
• Wenn F=qF', rekursiv F' [q=1], F' [q=0] bewerten Sie und iff akzeptieren Sie, den mindestens ein akzeptieren.
• Raumgebrauch: Die Zahl von Niveaus von recursion ist der Zahl von Variablen von F gleich. Der Betrag der an jedem Niveau von recursion versorgten Information ist (Werte der Formel für p=0 und p=1) unveränderlich. Deshalb ist der verwendete Gesamtraum geradlinig.

Das Gewinnen von Strategien für Spiele

Sieh Spielkompliziertheit für mehr Spiele, deren Vollständigkeit für PSPACE oder andere Kompliziertheitsklassen bestimmt worden ist.

Verallgemeinerte Erdkunde

• Auf dem Eingang

• Wenn b keinen aus dem Amt scheiden Rand hat, zurückweisen.
• Entfernen Sie sonst b und alle seine Ränder, nennen Sie diesen neuen Graphen G.
• Rekursiv geführt auf Eingängen, b>, wo jeder b die Endpunkte von Rändern von b sind.
• Weisen Sie zurück, wenn alle akzeptieren; akzeptieren Sie sonst.
• Raumgebrauch: Die Zahl von Niveaus von recursion ist der Zahl von Knoten in G gleich. Der Betrag der an jedem Niveau von recursion versorgten Information ist der Zahl von Knoten in G gleich. Deshalb ist der verwendete Gesamtraum geradlinig.

Die Bestimmung, ob ein regelmäßiger Ausdruck alle Schnuren erzeugt

In Anbetracht eines regelmäßigen Ausdrucks R, bestimmend, ob es alle Schnuren erzeugt (d. h., L(R) = Σ) ist PSPACE-abgeschlossen.

Siehe auch

• Ehrenfeucht-Fraïssé Spiel

• Abschnitt 8.3: PSPACE-Vollständigkeit, Seiten 283-94.

• Abschnitt 7.4: Polynomische Raumvollständigkeit, Seiten 170-77.

Außenverbindungen

• Rechenbetonte Kompliziertheit von Spielen und Rätseln
• Go/Baduk, Brettspiel: "Leitern" arbeiten auf diese Weise