ECCC-Report TR04-030https://eccc.weizmann.ac.il/report/2004/030Comments and Revisions published for TR04-030en-usFri, 09 Apr 2004 21:19:01 +0300
Paper TR04-030
| Kolmogorov complexity of enumerating finite sets |
Nikolay Vereshchagin
https://eccc.weizmann.ac.il/report/2004/030Solovay 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.
Fri, 09 Apr 2004 21:19:01 +0300https://eccc.weizmann.ac.il/report/2004/030