We study the relation between deterministic and randomized enumerating Kolmogorov complexity of sets S ? ?. Let D(S) be the length of a shortest input on which a fixed optimal deterministic machine enumerates S, and let R(S) be the probability that a fixed optimal randomized machine enumerates S. It is easy to see that ?log R(S) ? D(S) + O(log D(S)) for every S; the converse direction is much harder. Solovay proved D(S) ? ?3 log R(S) + O(log log(1/R(S))) for all S, while for finite sets the sharper bound with the constant 2 is known.
We show that the case of infinite sets carries no extra cost: any inequality of the form D(F) ? ?? log R(F) + O(log log(1/R(F))) with a computable ?, valid for all finite F, automatically extends to all sets. More generally, we prove a single dichotomy from which such transfer results follow for an arbitrary computable non-decreasing bound, and which also shows that every c.e. set S has a finite subset F such that F has at least as large deterministic complexity as S but randomized one approximately the same or lower. Our result makes qualitative progress on a problem studied by Solovay in 1977 by showing that the search for the optimal constant can be reduced to a purely combinatorial question about a game played with finite sets. In particular, our result yields D(S) ? ?2 log R(S) + O(log log(1/R(S))) for every S, improving Solovay's constant 3 to 2.
A little improvement of the exposition
We reduce the best-known upper bound on the length of a program that enumerates a set in terms of the probability of it being enumerated by a random program. We prove a general result that any linear upper bound for finite sets implies the same linear bound for infinite sets.
So far, the best-known upper bound was given by Solovay. He showed that the minimum length of a program enumerating a subset $S$ of natural numbers is bounded by minus three binary logarithms of the probability that a random program will enumerate S. Later, Vereshchagin showed that the constant can be improved from three to two for finite sets. In this work, using the method proposed by Solovay, we demonstrate that any bound for finite sets implies the same for infinite sets, modulo logarithmic factors. Using Vereshchagin's result, we improve the current best-known upper bound from three to two.