Колмогоровская сложность

Колмогоровскую сложность можно рассматривать как способ измерения количества информации в строке.

Но как понять, какое количество информации содержит в себе строка? Один из классических способов — это подсчет количества битов (число, пропорциональное длине строки). Рассмотрим следующий пример:

00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

Понятно, что эту строку можно описать более компактно на естественном языке, "128 нулей", всего 9 символов.

Можем дать следующее определение. Количество информации, которое несет строка — это размер архива, полученного сжатием строки каким-то конкретным архиватором (например, LZW). Это более нетривиальная задача, но мы можем придумать строку, которая явно несет в себе мало информации, но которую архиватор тем не менее не сожмет.

Еще более сильное определение. Количество информации, которое несет строка — это размер архива, сжатого максимальным образом, самым лучшим архиватором. Но тогда встает вопрос, почему такой архиватор существует. На самом деле он есть, и в некотором смысле колмогоровская сложность строки — это размер наименьшей программы, которая печатает эту строку.

Определения

Определение:

Назовём декомпрессором [math]D : \{0, 1\}^* \to \left[\begin{array}{l}\{0, 1\}^* \\ \bot\end{array}\right.[/math] алгоритм, восстанавливающий разжатый текст из сжатого.

Примечание: для простоты мы будем рассматривать бинарный алфавит, но все утверждения мы можем обобщить на строки произвольного алфавита.

Относительно каждого декомпрессора мы можем определить понятие сложности строки:

Определение:

Пусть [math]x \in \{0, 1\}^* [/math], тогда назовем колмогоровской сложностью строки [math]K_D(x) = \min \limits_{y}\ \{|y|\ |\ D(y) = x \}[/math], размер минимальной строки [math]y[/math], такой, что [math]D(y) = x[/math]. Если такого [math]y[/math] не существует, тогда [math]K_D(x) = +\infty[/math].

Примеры

• [math]D(x) = x[/math], тогда [math]K_D(x) = |x|[/math]
• [math]D(x) = xx[/math], тогда [math]K_D(0000) = 2, K_D(01) = +\infty [/math]

Определение:

Будем говорить, что декомпрессор [math]D_1[/math] лучше, чем декомпрессор [math]D_2[/math], если [math]\exists c:\forall x \in \{0, 1\}^*\ K_{D_1}(x) \leqslant K_{D_2}(x) + c[/math].