Complexity seminar

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