Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR01-086 | 29th October 2001 00:00

Kolmogorov Complexity Conditional to Large Integers

RSS-Feed




TR01-086
Authors: Nikolay Vereshchagin
Publication: 28th November 2001 16:39
Downloads: 1435
Keywords: 


Abstract:

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.



ISSN 1433-8092 | Imprint