Theoretical Computer Science

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"


  • 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.

Comments (2)

  • +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