Enumerating Complexity Revisited

Alexander Shekhovtsov, Georgii Zakharov

Consider a subset of positive integers $S$. In this paper, we reduce the upper bound on the length of a minimum program that enumerates $S$ in terms of the probability of $S$ being…