TR01-086 Authors: Nikolay Vereshchagin

Publication: 28th November 2001 16:39

Downloads: 1561

Keywords:

Assume that for almost all n Kolmogorov complexity

of a string x conditional to n is less than m.

We prove that in this case

there is a program of size m+O(1) that given any sufficiently large

n outputs x.