Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with initial segment:
TR01-083 | 29th October 2001
Nikolay Vereshchagin

An enumerable undecidable set with low prefix complexity: a simplified proof

Revisions: 1

We present a simplified proof of Solovay-Calude-Coles theorem
stating that there is an enumerable undecidable set with the
following property: prefix
complexity of its initial segment of length n is bounded by prefix
complexity of n (up to an additive constant).

more >>>

TR01-087 | 29th October 2001
Bruno Durand, Alexander Shen, Nikolay Vereshchagin

Descriptive complexity of computable sequences

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 ... more >>>

ISSN 1433-8092 | Imprint