Short lists with short programs in short time

Bruno Bauwens, Anton Makhlin, Nikolay Vereshchagin +1

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 th…