Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR04-030 | 9th March 2004 00:00

Kolmogorov complexity of enumerating finite sets

RSS-Feed




TR04-030
Authors: Nikolay Vereshchagin
Publication: 9th April 2004 21:19
Downloads: 1107
Keywords: 


Abstract:

Solovay has proven that
the minimal length of a program enumerating a set A
is upper bounded by 3 times the absolute value of the
logarithm of the
probability that a random program will enumerate A.
It is unknown whether one can replace the constant
3 by a smaller constant.
In this paper, we show that the constant 3 can be replaced
by the constant 2 for finite sets A.



ISSN 1433-8092 | Imprint