Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > THE A PRIORI PROBABILITY:
Reports tagged with the a priori probability:
TR04-030 | 9th March 2004
Nikolay Vereshchagin

Kolmogorov complexity of enumerating finite sets

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




ISSN 1433-8092 | Imprint