8
$\begingroup$

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?
$\endgroup$
  • $\begingroup$ Any further references are welcomed. Thank you! :) $\endgroup$ – Michael Wehar Nov 19 '16 at 1:00
  • 1
    $\begingroup$ 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." ​ ​ ​ ​ $\endgroup$ – user6973 Nov 19 '16 at 3:13
  • $\begingroup$ @RickyDemer This is great!! Thank you for sharing. :) $\endgroup$ – Michael Wehar Nov 19 '16 at 3:16
  • 1
    $\begingroup$ 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. ​ ​ ​ ​ $\endgroup$ – user6973 Nov 19 '16 at 6:14
  • 3
    $\begingroup$ 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? $\endgroup$ – Emil Jeřábek Nov 19 '16 at 10:19
2
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ 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? ​ ​ ​ ​ $\endgroup$ – user6973 Nov 19 '16 at 17:33
  • $\begingroup$ 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$? $\endgroup$ – Michael Wehar Nov 29 '16 at 8:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.