Невычислимость алгоритмического информационного расстояния

С середины 20го века, ученые старались изучать Колмогоровскую сложность. В результате появилось нормализованное информационное расстояние, которое является объектом, сильно связанным с префиксной Колмогоровской сложностью. Известно, что из невычислимости Колмогоровской сложности следует невычислимость и нормализованного информационного расстояния. В последние годы вышло несколько работ, которые показывают сложность в аппроксимации этой величины. В этой работе доказывается нижняя оценка в $\Omega(n)$ количества осцилляций, которое может иметь аппроксимация функции, тесно связанной с нормализованным информационным расстоянием (с длиной строки в условии префиксной Колмогоровской сложности). Это улучшает оценку в $\Omega(n/ \log n)$, доказанную нами ранее. Этот результат доказывается с помощью теории игр: в работе вводится некоторая игра, такая что из существования выигрышной стратегии для одного из игроков выводится необходимая оценка. После этого, в работе представляется выигрышная стратегия, которая и доказывает итоговую оценку.