Kolmogorov Complexity and Solovay Functions

Laurent Bienvenu & Rod Downey
Solovay (1975) proved that there exists a computable upper bound~$f$ of the prefix-free Kolmogorov complexity function~$K$ such that $f(x)=K(x)$ for infinitely many~$x$. In this paper, we consider the class of computable functions~$f$ such that $K(x) \leq f(x)+O(1)$ for all~$x$ and $f(x) \leq K(x)+O(1)$ for infinitely many~$x$, which we call Solovay functions. We show that Solovay functions present interesting connections with randomness notions such as Martin-L\"of randomness and K-triviality.
This data center is not currently reporting usage information. For information on how your repository can submit usage information, please see our documentation.
We found no citations for this text. For information on how to provide citation information, please see our documentation.