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

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

24 March 2025, 16.30 CET = 18.30 Moscow time

Andrei Romashchenko
On the reduction of Kolmogorov complexity by relativization

Alexander Shen asked the following question: let us have a tuple of strings x_1,...,x_n and their Kolmogorov complexities v=(C(x_1),...,C(x_n)). For every string y we get the values of conditional complexities w=(C(x_1|y),...,C(x_n|y)). Which values w of conditional complexities can we obtain? Can we, for example, find a y such that each value C(x_i|y) is (approximately) a half of C(x_i)?

We show that the answer to the last question is positive for n=1 (trivial) and for n=2 (can be proven with Muchnik's theorem on condtional descriptions or with Shen's topological argument).

For n=3, the answer is negative: there exists a triple (x_1, x_2, x_3) such that C(x_1)=2n, C(x_2)=2n, C(x_3)=3n, and there is no y such that C(x_1|y)=n, C(x_2|y)=n, C(x_3|y)=1.5n. This negative result follows from combinatorial properties of discrete projective planes over prime fields (Bourgain, Katz, Tao).

➰ ВК