In this paper, we show that the constant 3 in Solovay's inequality, relating the negative logarithm of the a priori probability and Kolmogorov complexity for the problems of enumerating finite sets, can be replaced by the constant 2.

, ,
Information Processing Letters
Quantum Information Processing
Quantum Computing and Advanced System Research

Vereshchagin, N.K. (2007). Kolmogorov complexity of enumerating finite sets. Information Processing Letters, 103(1), 34–39.