PSPACE
Im Computerkomplexitätstheorie, PSPACE ist der Satz von allen Entscheidungsprobleme das kann durch a gelöst werden Turing Maschine Verwendung einer Polynom Menge an Platz.
Formale Definition
Wenn wir durch den Raum bezeichnen (t(n)), die Menge aller Probleme, die durch gelöst werden können Turing -Maschinen Verwendung O(t(n)) Platz für eine Funktion t der Eingangsgröße nund dann können wir PSPACE formell als definieren als[1]
PSPACE ist ein strenger Superet des Satzes von Kontextsensitive Sprachen.
Es stellt sich heraus, dass die Turing -Maschine es zulässt Nichtdeterministisch Fügt keine zusätzliche Leistung hinzu. Durch Savitchs Theorem,[2] Npspace entspricht PSPACE, im Wesentlichen, weil eine deterministische Turing -Maschine a simulieren kann Nichtdeterministische Turing-Maschine ohne viel mehr Platz zu benötigen (obwohl es viel mehr Zeit verbraucht).[3] Auch die Ergänzungen Von allen Problemen in PSPACE sind auch in PSPACE, was bedeutet, dass CO-PSPACE = PSPACE.
Beziehung zu anderen Klassen
Die folgenden Beziehungen sind zwischen PSPACE und den Komplexitätsklassen bekannt Nl, P, Np, PH, Nachfolger und Expace (Beachten Sie, dass ⊊, was bedeutet, strenge Eindämmung, nicht dasselbe ist wie ⊈):
Aus der dritten Zeile folgt, dass sowohl in der ersten als auch in der zweiten Zeile mindestens eine der festgelegten Hälfte streng sein muss, aber nicht weiß, welches. Es wird weithin vermutet, dass alle streng sind.
Die Eindämme in der dritten Zeile sind beide als streng bekannt. Der erste folgt aus der direkten Diagonalisierung (der Raumhierarchie Theorem, Nl ⊊ npspace) und die Tatsache, dass pSpace = npspace über Savitchs Theorem. Der zweite folgt einfach aus dem Theorem der Weltraumhierarchie.
Die schwierigsten Probleme in der PSPACE sind die PSPACE-Vervollständigungsprobleme. Sehen PSPACE-Complete Beispiele für Probleme, bei denen vermutet wird, dass sie in PSPACE, jedoch nicht in NP sind.
Verschlusseigenschaften
Der PSPACE der Klasse wird im Operationen geschlossen Union, Ergänzung, und Kleene Star.
Andere Charakterisierungen
Eine alternative Charakterisierung von PSPACE ist die Reihe von Problemen Wechsel Turing Machine In der Polynomzeit, manchmal als aptime oder nur ap genannt.[4]
Eine logische Charakterisierung von PSPACE von Beschreibende Komplexität Theorie ist, dass es die Gruppe von Problemen ist, die ausdrucksfähig sind Logik zweiter Ordnung mit Hinzufügen von a Transitive Schließung Operator. Eine vollständige transitive Schließung ist nicht erforderlich; Ein kommutatives transitives Verschluss und sogar schwächere Formen reicht aus. Es ist die Zugabe dieses Bedieners, der (möglicherweise) PSPACE von unterscheidet PH.
Ein wichtiges Ergebnis der Komplexitätstheorie ist, dass PSPACE als alle von einem bestimmten Sprachen erkennbaren Sprachen charakterisiert werden kann Interaktives Proof -System, derjenige, der die Klasse definiert IP. In diesem System gibt es einen allmächtigen Prover, der versucht, einen randomisierten Polynomzeitprüfer zu überzeugen, dass sich eine Saite in der Sprache befindet. Es sollte in der Lage sein, den Verifizierer mit hoher Wahrscheinlichkeit zu überzeugen, ob sich die Saite in der Sprache befindet, aber nicht in der Lage sein sollte, ihn zu überzeugen, außer mit geringer Wahrscheinlichkeit, wenn sich die Saite nicht in der Sprache befindet.
PSPACE kann als Quantenkomplexitätsklasse charakterisiert werden QIP.[5]
PSPACE ist auch gleich pCTC, Probleme lösbar durch klassische Computer mithilfe geschlossene zeitlichartige Kurven,[6] sowie zu bqpCTC, Probleme lösbar durch Quantencomputer mit geschlossenen zeitlichen Kurven.[7]
PSPACE-Completness
Eine Sprache B ist PSPACE-Complete Wenn es in PSPACE ist und es PSPACE-HART ist, was bedeutet für alle A ∈ Pspace, , wo bedeutet, dass es a gibt Polynomzeit viele eins Reduktion aus A zu B. PSPACE-Complete-Probleme sind für die Untersuchung von PSPACE-Problemen von großer Bedeutung, da sie die schwierigsten Probleme in der PSPACE darstellen. Eine einfache Lösung für ein PSPACE-Complete-Problem zu finden, würde bedeuten, dass wir eine einfache Lösung für alle anderen Probleme in der PSPACE haben, da alle PSPACE-Probleme auf ein PSPACE-Complete-Problem reduziert werden können.[8]
Ein Beispiel für ein PSPACE-Complete-Problem ist das Quantifiziertes Problem der Booleschen Formel (normalerweise abgekürzt zu QBF oder Tqbf; das T steht für "wahr").[8]
Anmerkungen
- ^ Arora & Barak (2009) S.81
- ^ Arora & Barak (2009) S.85
- ^ Arora & Barak (2009) S.86
- ^ Arora & Barak (2009) S.100
- ^ Rahul Jain; Zhengfeng Ji; Sarvagya Upadhyay; John Watrous (Juli 2009). "QIP = PSPACE". Arxiv:0907.4737 [Quant-Ph].
- ^ S. Aaronson (März 2005). "NP-Vervollständigungsprobleme und physische Realität". Sigact News. Arxiv:Quant-Ph/0502072. Bibcode:2005quant.ph..2072a. doi:10.1145/1052796.1052804. S2CID 18759797..
- ^ Watrous, John; Aaronson, Scott (2009). "Geschlossene zeitlichere Kurven machen Quanten- und Klassik -Computeräquivalent". Verfahren der Royal Society A: Mathematische, physische und technische Wissenschaften. 465 (2102): 631. Arxiv:0808.2669. Bibcode:2009RSPSA.465..631a. doi:10.1098/rspa.2008.0350. S2CID 745646.
- ^ a b Arora & Barak (2009) S.83
Verweise
- Arora, Sanjeev; Barak, Boaz (2009). Rechenkomplexität. Ein moderner Ansatz. Cambridge University Press. ISBN 978-0-521-42426-4. Zbl 1193.68112.
- Sipser, Michael (1997). Introduction to the Theory of Computation. PWS Publishing. ISBN 0-534-94728-x. Abschnitt 8.2–8.3 (die Klasse PSPACE, PSPACE-Completness), S. 281–294.
- Papadimitriou, Christos (1993). Rechenkomplexität (1. Aufl.). Addison Wesley. ISBN 0-201-53082-1. Kapitel 19: Polynomraum, S. 455–490.
- Sipser, Michael (2006). Introduction to the Theory of Computation (2. Aufl.). Thomson -Kurs -Technologie. ISBN 0-534-95097-3. Kapitel 8: Raumkomplexität
- Komplexitätszoo: PSPACE