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