Consequences of a distillation algorithm for PSPACE

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?

Asked by user14207 (4,900 )
Nov 19, 2016 at 00:59