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

Колмогоровская сложность — это мера количества вычислительных ресурсов, необходимых для описания объекта (например, строки символов, числа или последовательности данных). Формально, колмогоровская сложность строки определяется как длина кратчайшей программы (на фиксированном языке программирования), которая выводит эту строку и завершает работу. Понятие введено советским математиком Андреем Николаевичем Колмогоровым в 1960-х годах и является фундаментальным понятием в теории алгоритмов, теории информации и теории вычислимости.

История

Идея измерения сложности объекта через длину его описания восходит к работам Рэя Соломонова (1960), который предложил «алгоритмическую теорию вероятности». Однако именно Андрей Колмогоров в 1963—1965 годах дал строгое определение, независимо от Соломонова, и заложил основы теории сложности. В 1966 году Колмогоров опубликовал статью «Три подхода к определению понятия „количество информации“», где сформулировал алгоритмический подход к информации. Позднее, в 1970-х годах, Леонид Левин (СССР/США) и Грегори Чайтин (Аргентина/США) независимо развили теорию, введя понятие алгоритмической вероятности и сложности по Чайтину.

Определение

Формальное определение

Пусть \( x \) — конечная строка символов над некоторым алфавитом \( \Sigma \). Пусть \( U \) — универсальная машина Тьюринга (или фиксированный язык программирования). Колмогоровская сложность \( K_U(x) \) строки \( x \) определяется как:

\[ K_U(x) = \min\{ |p| : U(p) = x \} \]

где \( p \) — программа (строка), подаваемая на вход машине \( U \), а \( |p| \) — длина программы (в битах или символах). Если ни одна программа не выводит \( x \), то \( K_U(x) \) считается бесконечной.

Инвариантность

Колмогоровская сложность зависит от выбора универсальной машины \( U \), но с точностью до аддитивной константы. Для любых двух универсальных машин \( U \) и \( V \) существует константа \( C_{UV} \) (зависящая только от машин), такая что:

\[ |K_U(x) - K_V(x)| \le C_{UV} \]

для всех строк \( x \). Это свойство называется инвариантностью и позволяет говорить о «колмогоровской сложности» как об объективной характеристике, не привязанной к конкретному языку программирования.

Сложность по Чайтину

Грегори Чайтин предложил вариант определения, в котором программа должна быть самодостаточной (self-delimiting), то есть её длина должна быть однозначно определена без дополнительных маркеров конца. Для таких программ сложность обозначается \( H(x) \) и называется «сложностью по Чайтину» или «алгоритмической энтропией». Она удовлетворяет неравенству:

\[ H(x) \le K(x) + O(\log |x|) \]

Свойства

Основные свойства

1. Невычислимость: Функция \( K(x) \) не является вычислимой. Не существует алгоритма, который для произвольной строки \( x \) вычислял бы её колмогоровскую сложность. Это следует из парадокса Берри: если бы такой алгоритм существовал, можно было бы построить программу, которая находит строку с большой сложностью, что приводит к противоречию.

1. Верхняя граница: Для любой строки \( x \) длины \( n \) выполняется \( K(x) \le n + O(1) \) (программа может просто содержать саму строку). Для строк с регулярной структурой сложность может быть значительно меньше \( n \).

1. Нижняя граница: Существуют строки, для которых \( K(x) \ge n - c \) для некоторой константы \( c \) (не более \( 2^{-c} \) доля всех строк длины \( n \) имеет сложность меньше \( n - c \)). Такие строки называются алгоритмически случайными или несжимаемыми.

1. Субалдитивность: \( K(x, y) \le K(x) + K(y) + O(1) \), где \( K(x, y) \) — сложность пары строк.

1. Связь с энтропией Шеннона: Для случайных источников с распределением \( P \) математическое ожидание колмогоровской сложности \( \mathbb{E}[K(x)] \) приблизительно равно энтропии Шеннона \( H(P) \), но колмогоровская сложность определена для индивидуальных строк, а не для распределений.

Теорема о неполноте

Из невычислимости \( K(x) \) следует, что в любой непротиворечивой формальной системе (например, арифметике Пеано) существует лишь конечное число строк, для которых можно доказать, что их колмогоровская сложность превышает некоторую границу. Это — алгоритмический вариант теоремы Гёделя о неполноте.

Применение

Теория информации

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

Теория алгоритмов

• Доказательство неразрешимости: С помощью колмогоровской сложности доказывается неразрешимость многих задач, например, задачи о том, является ли строка случайной.
• Сложность описания: Используется в теории сложности вычислений для анализа минимальной длины программы, решающей задачу.

Компьютерные науки

• Сжатие данных: Алгоритмы сжатия (например, LZ77, LZW) стремятся приблизить колмогоровскую сложность, но не могут достичь её из-за невычислимости.
• Машинное обучение: Принцип минимальной длины описания (MDL) использует колмогоровскую сложность для выбора модели: лучшая модель минимизирует сумму длины описания модели и длины описания данных с помощью модели.
• Биоинформатика: Применяется для анализа геномных последовательностей, выявления функциональных участков.

Математика

• Теория вероятностей: Колмогоровская сложность используется для определения алгоритмической случайности (последовательность случайна, если её сложность близка к длине).
• Теория чисел: С помощью колмогоровской сложности доказываются существование трансцендентных чисел с определёнными свойствами.

Примеры

Пример 1: Регулярная строка

Строка «0101010101010101» (16 символов) может быть описана программой «повторить «01» 8 раз» длиной, скажем, 20 бит. Её колмогоровская сложность значительно меньше 16.

Пример 2: Случайная строка

Строка «1101000100110110» (16 символов), полученная подбрасыванием монеты, с высокой вероятностью не имеет короткого описания. Её колмогоровская сложность близка к 16.

Пример 3: Число π

Десятичное разложение числа π (3,14159…) имеет бесконечную длину, но может быть описано короткой программой, вычисляющей π. Поэтому колмогоровская сложность первых \( n \) цифр π равна \( O(\log n) \) (программа содержит алгоритм вычисления π и параметр \( n \)).

Критика и ограничения

1. Невычислимость: Невозможность точного вычисления колмогоровской сложности для произвольной строки ограничивает её практическое применение. Все оценки сложности являются приближёнными.
2. Зависимость от языка: Хотя инвариантность гарантирует, что разница между разными языками ограничена константой, для коротких строк эта константа может быть сравнима с длиной строки, что делает определение менее полезным.
3. Отсутствие вероятностной интерпретации: В отличие от энтропии Шеннона, колмогоровская сложность не даёт информации о вероятности появления строки в случайном процессе.
4. Сложность для практических алгоритмов: Алгоритмы сжатия, основанные на колмогоровской сложности, не могут быть реализованы на практике из-за невычислимости.

Интересные факты

• Андрей Колмогоров предложил это понятие, размышляя о природе случайности и информации. Он хотел дать определение «количества информации» в индивидуальном объекте, не зависящее от субъективного выбора вероятностной модели.
• Грегори Чайтин использовал колмогоровскую сложность для доказательства того, что в любой формальной системе существуют истинные, но недоказуемые утверждения о сложности чисел.
• Понятие алгоритмической случайности, тесно связанное с колмогоровской сложностью, используется в теории хаоса и квантовой механике для анализа непредсказуемости систем.
• В 2020-х годах колмогоровская сложность применяется в задачах машинного обучения для оценки сложности нейронных сетей и выбора оптимальной архитектуры.

Источники

1. Колмогоров А. Н. «Три подхода к определению понятия „количество информации“». — Проблемы передачи информации, 1965, т. 1, вып. 1, с. 3–11.
2. Чайтин Г. «Алгоритмическая теория информации». — В сб. «Кибернетический сборник», 1975, вып. 12, с. 5–38.
3. Li M., Vitányi P. «An Introduction to Kolmogorov Complexity and Its Applications». — 4th ed., Springer, 2019.
4. Шень А. Х. «Колмогоровская сложность и алгоритмическая случайность». — М.: МЦНМО, 2013.
5. Верещагин Н. К., Успенский В. А., Шень А. Х. «Колмогоровская сложность и алгоритмическая случайность». — М.: МЦНМО, 2013.