__
TR04-030 | 9th March 2004 00:00
__

#### Kolmogorov complexity of enumerating finite sets

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