Enumerating Complexity Revisited

Abstract

We study the relation between deterministic and randomized $\text{enumerating}$ Kolmogorov complexity of sets $S\subseteq \mathbb{N}$. 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)\le D(S)+O(\log D(S))$ for every $S$; the converse direction is much harder. Solovay proved $D(S)\le -3\log R(S)+O(\log \log \frac{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: $\text{any}$ inequality of the form $D(F)\le -\alpha \log R(F)+O(\log \log \frac{1}{R(F)})$ with a computable $\alpha$, 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)\le -2\log R(S)+O(\log \log \frac{1}{R(S)})$ for every $S$, improving Solovay's constant $3$ to $2$.