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-087 | 29th October 2001 00:00

Descriptive complexity of computable sequences

RSS-Feed




TR01-087
Authors: Bruno Durand, Alexander Shen, Nikolay Vereshchagin
Publication: 28th November 2001 16:39
Downloads: 1216
Keywords: 


Abstract:

We study different notions of descriptive complexity of
computable sequences. Our main result states that if for almost all
n the Kolmogorov complexity of the n-prefix of an infinite
binary sequence x conditional to n
is less than m then there is a program of length
m^2+O(1) that for almost all n given n as input prints the n-prefix
of x. We prove that this bound is tight up to a constant factor.



ISSN 1433-8092 | Imprint