Short Lists with Short Programs in Short Time

Abstract

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| <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> ) containing a O(1)-short program for x and this is essentially optimal because we prove that such a list must have size Ω(|x| <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> ). Finally we show that for some machines, computable lists containing a shortest program must have length Ω(2 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">|x|</sup> ).