Folgen eines Destillationsalgorithmus für PSPACE

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 ]$L$$\{ x_i \}_{i \in [t]}$$y$

(1) genau dann, wenn es so dassi ∈ [ t ] x i ∈ $y \in L$$i \in [t]$$x_i \in L$

(2) für ein Polynom$\vert y \vert \leq p(Max_{i\in[t]} \vert x_i \vert)$$p$

(3) Der Algorithmus berechnet in höchstens Zeit für ein Polynomq ( ∑ i ∈ [ t ] | x i | ) $y$$q(\sum_{i\in[t]}\vert x_i \vert)$$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 = Σ $NP$$coNP \subseteq NP/poly$$PH = \Sigma_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?

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 $L, R ⊆ \Sigma^*$$L\in coNP / 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 $L$$PSPACE \subseteq coNP/poly$