ECCC-Report TR01-086https://eccc.weizmann.ac.il/report/2001/086Comments and Revisions published for TR01-086en-usWed, 28 Nov 2001 16:39:45 +0200
Paper TR01-086
| Kolmogorov Complexity Conditional to Large Integers |
Nikolay Vereshchagin
https://eccc.weizmann.ac.il/report/2001/086Assume 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.
Wed, 28 Nov 2001 16:39:45 +0200https://eccc.weizmann.ac.il/report/2001/086