# 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?
• Any further references are welcomed. Thank you! :) – Michael Wehar Nov 19 '16 at 1:00
• By this paper and polynomial-time many-one reductions, "if there exists a distillation algorithm for an $NP$-complete problem, then" ​ NP $\subseteq$ coAM ​ and "there are non-uniform, statistical zero-knowledge proofs for all languages in NP." ​ ​ ​ ​ – user6973 Nov 19 '16 at 3:13
• @RickyDemer This is great!! Thank you for sharing. :) – Michael Wehar Nov 19 '16 at 3:16
• I now notice that the paper I linked to in fact only needs compression, which makes their results more general. ​ In particular, by Theorems 7.1 and 7.3, if there exists even a compression "algorithm for a $PSPACE$-complete problem" then PSPACE has non-uniform statistical zero-knowledge proofs. ​ ​ ​ ​ – user6973 Nov 19 '16 at 6:14
• I don't understand the last part of the question. AFAICS the existence of a distillation algorithm for a PSPACE-complete problem doesn't imply the existence of a dist algo for an NP-complete problem, or am I missing something? – Emil Jeřábek supports Monica Nov 19 '16 at 10:19

"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.
• You stated "also PSPACE collapses with it". In particular, I believe we get $\Sigma_3 = PSPACE$. I don't see a way to improve this, but I thought I would ask anyways. Can we get a better collapse that this? Say $\Sigma_2 = PSPACE$? – Michael Wehar Nov 29 '16 at 8:07