Gibt es eine Konsequenz mit der Existenz von $ \ Mathsf {pspace} $ - komplette spärliche Sprache wie bei Mahaney's theorem?

Question

Mahaney's theorem gibt an, dass das Vorhandensein von $ \ mathsf {np} $ -complete spärliche Sprache zu $ \ führen würde \mathsf {p= np} $ .Gibt es ein Ergebnisergebnis in Bezug auf die gleiche für die Komplexitätsklasse $ \ mathsf {pspace} $ , wie "Wenn es einen gibt$ \ mathsf {pspace} $ -Verkompleter spärlicher Sprache, $ \ mathsf {pp= pspace} $ "oder das Gleiche für jede andere Komplexitätsklasse in $ \ mathsf {pspace} $ ?

Answer 1

Ein schnelles Ergebnis ist, dass $ pspace=sigma_2 $ .

Zeigen Sie zuerst, dass $ PSPACE \ Subseteq p / poly $ , und als Ergebnis $ PSPACE \ Subseteq \ Sigma_2 $ (falls er findet, dass ein Eintrag einer Berechnungstabelle in p / poly ist, dann befindet sich auch in $ \ sigma_2 $ , da wir einen Stromkreis erraten und Überprüfen Sie die Richtigkeit lokal, wie beschrieben hier ).

um zu sehen warum, warum ein PSPACE-COMPANY SPARSE-Sprache $ s $ PSPACE in p / poly, gegeben $ l \ in pspace $ , lass $ f $ eine Reduzierung von $ L $ bis < Span-Klasse="Math-Container"> $ s $ . Beachten Sie, dass, wenn $ | f (x) | $ nur von $ | x | $ abhängig ist, dann < Span-Klasse="Math-Container"> $ l \ in p / poly $ Da können wir die Schaltkreise für $ F $ und für $ s $ (das ist in p / poly wegen spärlich). Um die Tatsache zu überwinden, dass $ F $ in der Länge der Ausgabe für dieselbe Eingabegröße variieren kann, beachten Sie, dass auf der Länge $ N $ -Angaben $ F $ Kann die Leistung der Länge erzeugen $ \ le n ^ C $ , so Gegebenen $ x $ Wir können als Hinweis auf alle $ | x | ^ C $ circuits für $ s $ auf Input-Größen $ 0,1, ..., | x | ^ C $ . Unter diesen Schaltungen haben wir die "richtige" Schaltung, die die Mitgliedschaft von $ F (x) $ in ermitteln kann> $ S $ .