Ученые научно-образовательной школы МГУ «Мозг, когнитивные системы, искусственный интеллект» установили, что математические объекты, сходные по содержащейся в них информации, могут существенно различаться при более строгой оценке. Для сравнения исследователи применили игровую технику. Результат уточняет способы оценки информационной зависимости между конечными объектами. Работа опубликована в журнале Information and Computation.
В основе исследования лежит сложность Колмогорова. Это математический способ оценить, насколько коротко можно описать объект с помощью программы. Если объект устроен просто, его можно описать коротко. Если объект близок к случайному, для его описания обычно нужна длинная программа
Чтобы понять, насколько связаны два объекта, используется условная сложность. Она показывает, насколько короткая программа нужна, чтобы получить один объект, если второй уже известен. Если два объекта можно легко восстановить друг из друга, считается, что они содержат почти одну и ту же информацию.
Однако у такого подхода есть более строгий вариант — полная условная сложность. В этом случае программа должна не только правильно работать на конкретном входе, но и быть определена для всех возможных входов. Это дополнительное требование может заметно изменить оценку связи между объектами.
Ранее было известно, что полная условная сложность может быть значительно больше обычной условной сложности. Но такие примеры строились искусственно и не были связаны с объектами, которые сами по себе представляют интерес для теории алгоритмической информации.
В новой работе рассмотрены естественные объекты, возникающие в теории сложности Колмогорова. Среди них — первое по алфавитному порядку слово заданной длины, сложность которого не меньше этой длины, а также число слов, сложность которых меньше заданного значения. Ранее было известно, что с точки зрения обычной условной сложности такие объекты могут содержать почти одну и ту же информацию.
В работе показано, что при более строгом подходе картина меняется. Обычная условная сложность между такими объектами может оставаться малой, а полная условная сложность — расти пропорционально размеру объекта. Это означает, что два объекта, которые выглядят почти одинаковыми по содержащейся информации в одном смысле, могут оказаться существенно различными в другом, более строгом смысле.
Для доказательства результата использована игровая техника. В статье рассматриваются специальные математические игры, с помощью которых строятся оптимальные языки программирования с нужными свойствами. Такой подход позволяет показать, что требование полной определённости программы действительно может приводить к росту сложности.
«Обычная условная сложность отвечает на вопрос, насколько коротко можно получить один объект из другого. Полная условная сложность добавляет важное ограничение: программа должна корректно работать как всюду определённая функция. Оказывается, это ограничение может существенно изменить оценку информационной зависимости даже для объектов, которые естественно возникают в теории сложности Колмогорова», — пояснил Николай Верещагин, профессор кафедры математической логики и теории алгоритмов механико-математического факультета МГУ.
Работа относится к фундаментальной математике. Её результат уточняет, в каком смысле конечные объекты можно считать содержащими одну и ту же информацию, и может быть полезен для дальнейших исследований в теории алгоритмической информации, сложности Колмогорова и теории вычислимости.