Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR01-083 | 9th January 2002 00:00

RSS-Feed




Revision #1
Authors: Nikolay Vereshchagin
Accepted on: 9th January 2002 00:00
Downloads: 3311
Keywords: 


Abstract:


Paper:

TR01-083 | 29th October 2001 00:00

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





TR01-083
Authors: Nikolay Vereshchagin
Publication: 27th November 2001 00:33
Downloads: 3212
Keywords: 


Abstract:

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



ISSN 1433-8092 | Imprint