Folgen eines Destillationsalgorithmus für PSPACE

9

Der folgende Begriff eines Destillationsalgorithmus stammt aus "Über Probleme ohne Polynomkerne".

Es sei eine Sprache gegeben. Ein Destillationsalgorithmus für nimmt eine gegebene Liste von Eingabezeichenfolgen und berechnet eine Ausgabezeichenfolge :L{ x i } i [ t ] yL{xi}i[t]y

(1) genau dann, wenn es so dassi [ t ] x iL.yLi[t]xiL

(2) für ein Polynomp|y|p(Maxi[t]|xi|)p

(3) Der Algorithmus berechnet in höchstens Zeit für ein Polynomq ( i [ t ] | x i | ) qyq(i[t]|xi|)q

Es wurde gezeigt, dass, wenn es einen Destillationsalgorithmus für ein vollständiges Problem gibt, . Außerdem ist PH = \ Sigma_3 .c o N P N P / p o l y P H = Σ 3NPcoNPNP/polyPH=Σ3

Siehe Details und Diskussion in:

  • "Unmöglichkeit der Instanzkomprimierung und prägnante PCPs für NP"
  • "Bei Problemen ohne Polynomkerne"
  • "Untergrenzen der Kernelisierung"

Fragen:

  • Könnte es einen Destillationsalgorithmus für ein PSPACE vollständiges Problem geben?
  • Wenn ein solcher Algorithmus existieren würde, welche Komplexitätsfolgen würden wir haben?
Michael Wehar
quelle
Weitere Referenzen sind willkommen. Vielen Dank! :)
Michael Wehar
1
Durch dieses Papier und Polynom-Zeit- Viel -Eins-Reduktionen, "wenn es einen Destillationsalgorithmus für ein vollständiges Problem gibt, dann" NP coAM und "gibt es ungleichmäßige statistische Null-Wissens-Beweise für alle Sprachen in NP. " NP
@ RickyDemer Das ist großartig !! Ich danke Ihnen für das Teilen. :)
Michael Wehar
1
Ich stelle jetzt fest, dass das Papier, mit dem ich verlinkt habe, tatsächlich nur komprimiert werden muss , wodurch die Ergebnisse allgemeiner werden. Insbesondere nach Satz 7.1 und 7.3 hat PSPACE ungleichmäßige statistische Null-Wissens-Beweise , wenn es sogar einen Komprimierungsalgorithmus für ein vollständiges Problem gibt. PSPACE
3
Ich verstehe den letzten Teil der Frage nicht. AFAICS Die Existenz eines Destillationsalgorithmus für ein PSPACE-vollständiges Problem impliziert nicht die Existenz eines Distalgo für ein NP-vollständiges Problem, oder fehlt mir etwas?
Emil Jeřábek

Antworten:

3

Satz 15.3 des kürzlich erschienenen Lehrbuchs "Parametrisierte Algorithmen" von Cygan et al. gibt Folgendes an:

"Sei zwei Sprachen. Wenn es eine OR-Destillation von L zu R gibt, dann ist " L C O N P / p o l yL,RΣLcoNP/poly

Ich denke also, wenn es eine ODER-Destillation von einer PSPACE-vollständigen Sprache zu sich selbst gibt, dann , dh nicht nur die kollabiert, sondern auch PSPACE kollabiert damit.P S P A C E c o N P / p o l yLPSPACEcoNP/poly

Michael Lampis
quelle
2
Satz 7.1 des Papiers, auf das ich in den Kommentaren verwiesen habe, ist qualitativ qualitativ besser. Behandelt Satz 15.3 dieses Buches Fehlergrenzen, die für einige Parameter größer sind als Punkt 2 von 7.1?
Sie sagten, "auch PSPACE bricht damit zusammen". Insbesondere glaube ich, dass wir . Ich sehe keinen Weg, dies zu verbessern, aber ich dachte, ich würde sowieso fragen. Können wir einen besseren Zusammenbruch bekommen als diesen? Sagen Sie ? Σ 2 = P S P A C E.Σ3=PSPACEΣ2=PSPACE
Michael Wehar