#матлог #учёба #спецсеминар

Kolmogorov seminar on complexity (for receive the zoom link, please email nikolay.vereshchagin@gmail.com)

5 October, 18:30 MSK

"How AI answers the questions about Kolmogorov complexity"

Cole Wyeth asked the following question: let m(x) be the discrete a priori probability and let a(x) and a(x|y) be continuous a priori probability (+ conditional one, when y is a discrete condition). Then there is an inequality (up to constant factors) for the probability of concatenation: a(xy) \le m(x) a(y|x)

Indeed, the right hand side corresponds to the generation process when first x is generated according to m(x) and then y is generated according to a(y|x). This can be rewritten as m(x)\ge a(xy)/a(y|x) and then as m(x) \ge \inf_y a(xy)/a(y|x)

Question: is the last inequality an equality up to O(1) factor?

I thought for a while and couldn't find the answer - then Alexey Milovanov (who formalized a lot of statements about Kolmogorov complexity with AI - this is another story worth telling) asked the LLMs about this, and they found a solution, and, moreover, explained it to me.

So we will discuss this solution (and maybe its history or other related questions).