Consequences of a distillation algorithm for PSPACE

Question

The following notion of a distillation algorithm comes from "On Problems Without Polynomial Kernels".

Let a language $L$ be given. A distillation algorithm for $L$ takes a given list of input strings $\{ x_i \}_{i \in [t]}$ and computes an output string $y$ such that:

(1) $y \in L$ if and only if there exists $i \in [t]$ such that $x_i \in L$

(2) $\vert y \vert \leq p(Max_{i\in[t]} \vert x_i \vert)$ for some polynomial $p$

(3) The algorithm computes $y$ in at most $q(\sum_{i\in[t]}\vert x_i \vert)$ time for some polynomial $q$

It has been shown that if there exists a distillation algorithm for an $NP$-complete problem, then $coNP \subseteq NP/poly$. Moreover, $PH = \Sigma_3$.

See details and discussion in:

• "Infeasibility of Instance Compression and Succinct PCPs for NP"
• "On Problems Without Polynomial Kernels"
• "Lower bounds on kernelization"

Questions:

• Could there exist a distillation algorithm for a $PSPACE$-complete problem?
• If such an algorithm existed, what complexity consequences would we get?

Answer 1

Theorem 15.3 of the recent "Parameterized Algorithms" textbook by Cygan et al. states the following:

"Let $L, R ⊆ \Sigma^*$ be two languages. If there exists an OR-distillation of L into R, then $L\in coNP / poly$"

So, I think that if there exists an OR-distillation from a PSPACE-complete language $L$ to itself, then $PSPACE \subseteq coNP/poly$, i.e. not only does the polynomial-hierarchy collapse, but also PSPACE collapses with it.