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). Generating a short program for a string is a fundamental problem
for example in learning theory.
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. This result has been improved to obtain
lists containing O(1)-short programs by Teutsch and by Zimand.
If we consider computable lists rather than polynomial time computable
lists, we obtain tight bounds for the list sizes:
* There exist computable functions that map every x to a list of size
O(|x|^2) containing a O(1)-short program for x.
* Every computable function generating lists containing c-short programs
for all x, computes infinitely often lists of size at least Omega(|x|^2/c^2).
The quadratic lower bound can be beaten using probabilistic... more