ECCC-Report TR13-007https://eccc.weizmann.ac.il/report/2013/007Comments and Revisions published for TR13-007en-usTue, 08 Jan 2013 15:39:22 +0200
Revision 1
| Short lists with short programs in short time |
Nikolay Vereshchagin,
Bruno Bauwens,
Marius Zimand,
Anton Makhlin
https://eccc.weizmann.ac.il/report/2013/007#revision1Given a machine $U$, a $c$-short program for $x$ is a string $p$ such that $U(p)=x$ and the length of $p$ is bounded by $c$ + (the length of a shortest program for $x$). We show that for any universal machine, it is possible to compute in polynomial time on input $x$ a list of polynomial size guaranteed to contain a $O(\log|x|)$-short program for $x$. We also show that there exist computable functions that map every $x$ to a list of size $O(|x|^2)$ containing a $O(1)$-short program for $x$ and this is essentially optimal because we prove that such a list must have size $\Omega(|x|^2)$. Finally we show that for some machines, computable lists containing a shortest program must have length $\Omega(2^{|x|})$.Tue, 08 Jan 2013 15:39:22 +0200https://eccc.weizmann.ac.il/report/2013/007#revision1
Paper TR13-007
| Short lists with short programs in short time |
Nikolay Vereshchagin,
Bruno Bauwens,
Marius Zimand,
Anton Makhlin
https://eccc.weizmann.ac.il/report/2013/007Given a machine $U$, a $c$-short program for $x$ is a string $p$ such that $U(p)=x$ and the length of $p$ is bounded by $c$ + (the length of a shortest program for $x$). We show that for any universal machine, it is possible to compute in polynomial time on input $x$ a list of polynomial size guaranteed to contain a $O(\log|x|)$-short program for $x$. We also show that there exist computable functions that map every $x$ to a list of size $O(|x|^2)$ containing a $O(1)$-short program for $x$ and this is essentially optimal because we prove that such a list must have size $\Omega(|x|^2)$. Finally we show that for some machines, computable lists containing a shortest program must have length $\Omega(2^{|x|})$.Tue, 08 Jan 2013 15:02:46 +0200https://eccc.weizmann.ac.il/report/2013/007