[КТИ_2016]: Short lists with short programs from programs

Speaker: Nikolay Vereshchagin - Higher School of Economics Let f_p be an optimal Goedel numbering of the family of computable functions (in Schnorr’s sense), where p ranges over binary strings. Assume that a list of strings L(p) is computable from p and for all p contains a f-program for f_p whose length is at most eps bits larger that the length of shortest f-programs for f_p. We show that for infinitely many p the list L(p) must have exponential in (|p|-eps) strings. Here eps is an arbitrary function of