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

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

<p>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.</p>

CC BY-SA 3.0
2016-11-29T08:07:19.243Z
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
CC BY-SA 3.0
2016-11-19T16:30:54.743Z
2016-11-19T16:30:54.743Z
Michael Lampis
<p>The following notion of a distillation algorithm comes from "On Problems Without Polynomial Kernels".</p>

<blockquote>
  <p>Let a language $L$ be given.  A <strong>distillation algorithm</strong> for $L$ takes a given
  list of input strings $\{ x_i \}_{i \in [t]}$ and computes an output string
  $y$ such that:</p>
  
  <p>(1) $y \in L$ if and only if there exists $i \in [t]$ such that $x_i \in L$</p>
  
  <p>(2) $\vert y \vert \leq p(Max_{i\in[t]} \vert x_i \vert)$ for some polynomial $p$</p>
  
  <p>(3) The algorithm computes $y$ in at most $q(\sum_{i\in[t]}\vert x_i \vert)$ time for some polynomial $q$</p>
</blockquote>

<p>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$.</p>

<blockquote>
  <p>See details and discussion in:</p>
  
  <ul>
  <li>"Infeasibility of Instance Compression and Succinct PCPs for NP"</li>
  <li>"On Problems Without Polynomial Kernels"</li>
  <li>"Lower bounds on kernelization"</li>
  </ul>
</blockquote>

<p><strong>Questions:</strong></p>

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

CC BY-SA 3.0
2016-11-19T01:00:12.543Z
Any further references are welcomed.  Thank you!  :)
Michael Wehar
CC BY-SA 3.0
2016-11-19T03:16:04.530Z
@RickyDemer This is great!!  Thank you for sharing.  :)
Michael Wehar
CC BY-SA 3.0
2016-11-19T07:49:46.620Z
@RickyDemer Thank you again for pointing me to this!  :)
Michael Wehar
CC BY-SA 3.0
2016-11-19T10:19:18.257Z
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
CC BY-SA 3.0
2016-11-21T18:52:42.347Z
@EmilJeřábek This is a good point that I didn't realize.  I will make adjustments to my question.  When I was looking at it, I was considering whether a certain parameterized problem has a polynomial kernel which would imply that it has a distillation algorithm.  If this certain PSPACE-complete problem has a polynomial kernel, then a certain NP-complete problem has a polynomial kernel.  So the polynomial kernel for PSPACE does imply for NP, but the distillation for PSPACE might not imply distillation for NP unless I'm missing something.  :)
Michael Wehar
<cc.complexity-theory><np-hardness><parameterized-complexity><polynomial-hierarchy><pspace>
Consequences of a distillation algorithm for PSPACE
Michael Wehar
# Consequences of a distillation algorithm for PSPACE

(Asked by: username_0 on 2016-11-19)

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?

**Tags:** cc.complexity-theory, np-hardness, parameterized-complexity, polynomial-hierarchy, pspace
> **Comments:**
> **username_0**: Any further references are welcomed.  Thank you!  :)  
> **username_0**: @RickyDemer This is great!!  Thank you for sharing.  :)  
> **username_0**: @RickyDemer Thank you again for pointing me to this!  :)  
> **username_1**: 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?  
> **username_0**: @EmilJeřábek This is a good point that I didn't realize.  I will make adjustments to my question.  When I was looking at it, I was considering whether a certain parameterized problem has a polynomial kernel which would imply that it has a distillation algorithm.  If this certain PSPACE-complete problem has a polynomial kernel, then a certain NP-complete problem has a polynomial kernel.  So the polynomial kernel for PSPACE does imply for NP, but the distillation for PSPACE might not imply distillation for NP unless I'm missing something.  :)  

---

## 1 answers

### Answer by username_2 on 2016-11-19. Score: 3 | Accepted answer

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:**
> **username_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$?  

---

