Approximating Kolmogorov complexity

Abstract

It is well known that the Kolmogorov complexity function (the minimal length of a program producing a given string, when an optimal programming language is used) is not computable and, moreover, does not have computable lower bounds. In this paper we investigate a more general question: can this function be approximated? By approximation we mean two things: firstly, some (small) difference between the values of the complexity function and its approximation is allowed; secondly, at some (rare) points the values of the approximating function may be arbitrary.

For some values of the parameters such approximation is trivial (e.g., the length function is an approximation with error d except for a $\mathit{O}\mathrm{(}{2}^{-\mathit{d}}\mathrm{)}$ fraction of inputs). However, if we require a significantly better approximation, the approximation problem becomes hard, and we prove it in several settings. Firstly, we show that a finite table that provides good approximations for Kolmogorov complexities of n-bit strings, necessarily has high complexity. Secondly, we show that there is no good computable approximation for Kolmogorov complexity of all strings. In particular, Kolmogorov complexity function is neither generically nor coarsely computable, as well as its approximations, and the time-bounded Kolmogorov complexity (for any computable time bound) deviates significantly from the unbounded complexity function. We also prove hardness of Kolmogorov complexity approximation in another setting: the mass problem whose solutions are good approximations for Kolmogorov complexity function is above the halting problem in the Medvedev lattice. Finally, we mention some proof-theoretic counterparts of these results.

A preliminary version of this paper was presented at CiE 2019 conference (In Computing with Foresight and Industry – 15th Conference on Computability in Europe, CiE 2019, Durham, UK, July 15–19, 2019, Proceedings (2019) 230–239 Springer).