Seminar Algorithms and Complexity group CWI

Speaker: Nikolay Vereshchagin (Moscow State University)

Title: Short list of 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 an O(log|x|)-short program for x. We also show that there exist computable functions that map every x to a list of size |x|^2 containing an O(1)-short program for x and this is essentially optimal because we prove that such a list must have size Omega(|x|^2).