Short Lists with Short Programs in Short Time
Bruno Bauwens, Anton Makhlin, Nikolay Vereshchagin, Marius Zimand · 2013
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 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 Ω(|x|2). Finally we show that for some machines, computable lists containing a shortest program must have length Ω(2|x|).