Кафедра математической логики и теории алгоритмов

Механико-математического факультета МГУ


Колмогоровская сложность (сложность описаний) (Н. К. Верещагин, В. Н. Крупский, А. Шень)

Колмогоровскую сложность слова в данном алфавите можно определить как длину в битах кратчайшей программы, печатающей это слово. Интуитивно, сложность x равна количеству информации в x. Например, сложность достаточно длинной последовательности из одних нулей примерно равна сложности двоичной записи её длины. А сложность «случайной» последовательности примерно равна её длине. Последнюю фразу можно принять за определение случайной последовательности и на этом основании строить теорию вероятностей как науку о свойствах случайных последовательностей. Например, закон больших чисел будет сформулирован так: в любой случайной последовательности доля единиц примерно равна 1/2. (В обычной формулировке закон больших чисел говорит, что в большинстве последовательностей доля единиц примерно равна 1/2.) На том же основании можно построить и математическую статистику.

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