Топологические доказательства существования и колмогоровская сложность.
Аннотация
Когда-то Михаил Вьюгин доказал такой результат: если сложность слова $x
$ больше $2n$, то можно найти такое слово $y$, что обе условные
сложности $K(x|y)$ и $K(y|x)$ будут равны $n+O(1)$. Доказательство
использовало игровой метод. Удивительным образом оказывается, что
достаточно более слабого условия $K(x)>n+O(\log n)$, и это можно
установить совсем простым топологическим рассуждением. Будут обсуждены
и некоторые другие возможные приложения такого рода рассуждений.