Short lists with short programs from programs

255 views · Published 28 April 2016 · 1:27:30 · Indexed 20 November 2026

Channel: ФКН НИУ ВШЭ · 2016 · Education

Watch on YouTube

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 an f-program for f_p whose length is at most eps bits larger than 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 p.

Speaker: Professor Nikolay Vereshchagin, head of the Laboratory of Theoretical Computer Science, HE University.

Workshop on Theoretical Computer Science 2016: https://cs.hse.ru/en/big-data/tcs-lab/tcs2016/
Faculty of Computer Science: https://cs.hse.ru/en/
Follow us: https://www.facebook.com/hsefcs, https://twitter.com/CS_HSE

More from this channel