All reports by Author Anton Makhlin:

__
TR13-007
| 8th January 2013
__

Bruno Bauwens, Anton Makhlin, Nikolay Vereshchagin, Marius Zimand#### Short lists with short programs in short time

Revisions: 1

Bruno Bauwens, Anton Makhlin, Nikolay Vereshchagin, Marius Zimand

Given 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 ... more >>>