- cc.complexity-theory np-hardness parameterized-complexity polynomial-hierarchy pspace
- Updated Tue, 07 Jun 2022 11:55:31 GMT

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

Let a language $L$ be given. A

distillation algorithmfor $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?

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.

- +2 – Theorem 7.1 of the paper I linked to in the comments is strictly qualitatively better. Does Theorem 15.3 of that book handle larger-for-some-parameters error bounds than item 2 of 7.1? — Nov 19, 2016 at 17:33
- +0 – 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$? — Nov 29, 2016 at 08:07