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