Do you have a good reference for the Levin bound? My attempts at finding a relevant paper all failed.
The second Towards Data Science post references this paper, which is also the main reference through which Levin’s result is mentioned in the first paper you post. So I assume reading these references should be enough to get the gist.
There is a proof of it in “An Introduction to Kolmogorov Complexity and Its Applications” by Ming Li & Paul Vitanyi.
Do you have a good reference for the Levin bound? My attempts at finding a relevant paper all failed.
The second Towards Data Science post references this paper, which is also the main reference through which Levin’s result is mentioned in the first paper you post. So I assume reading these references should be enough to get the gist.
There is a proof of it in “An Introduction to Kolmogorov Complexity and Its Applications” by Ming Li & Paul Vitanyi.