ИИ закрыл задачу теории связи, открытую с 2001 года

Дмитрис Папаилиопулос, исследователь Microsoft Research, рассказал, как ИИ-модели GPT-5.6 и Claude Fable 5 решили задачу MIMO-детекции, которая оставалась открытой с 2001 года. Вопрос заключался в том, существует ли быстрый алгоритм, который достигает того же порога отношения сигнал/шум, что и полный перебор. Папаилиопулос, работавший над этой проблемой ещё аспирантом в 2009 году, задал его двум моделям. GPT-5.6 выдал первое доказательство примерно за 30 минут, но на проверку ушло пять дней. «Верификация — безумное бутылочное горлышко», — отметил исследователь.

MIMO-детекция — это задача восстановления переданных битов в системах с несколькими антеннами, используемых в Wi-Fi и 5G. Передатчик с N антеннами отправляет N битов, которые смешиваются в эфире, и приёмник должен восстановить исходные данные. Оптимальный метод — полный перебор всех 2^N комбинаций, но он вычислительно сложен. В 1989 году Серхио Верду доказал, что задача NP-трудна в худшем случае. Однако для случайных матриц, характерных для реальных каналов, теоретики информации выяснили, что при отношении сигнал/шум выше порога 2 log N восстановление возможно с вероятностью, стремящейся к единице. Вопрос был в том, существует ли полиномиальный алгоритм, достигающий этого порога.

История вопроса полна драматизма. В 2001 году Хассиби и Викало предложили Sphere Decoder, но через четыре года Ялден и Оттерстен показали, что его сложность всё равно экспоненциальна. Поле пробовало полуопределённые релаксации, AMP-методы и алгоритмы статистической физики, но строгих доказательств не было. Единственным строгим результатом стала box relaxation в 2020 году, но она работала только с порога 4 log N — вдвое хуже. Активность затухла, и вопрос завис.

Папаилиопулос решил вернуться к задаче, вдохновившись успехами ИИ в математике. Он выбрал самый амбициозный вопрос и заранее понимал, что проверка будет сложной. Обе модели ответили одинаково: зазора нет, полиномиальный алгоритм работает с порога 2 log N. GPT-5.6 предложил доказательство на основе AMP, а Claude Fable 5 — алгоритм с грубой линейной прикидкой и жадными переворотами битов. По вердикту GPT, доказательство Fable было «по большей части неверным, но спасаемым». Папаилиопулос оставил алгоритм Fable и попросил GPT исправить доказательство. Тот справился, и итоговое доказательство стало результатом совместной работы моделей.

Этот случай иллюстрирует ключевую проблему использования ИИ в математике: генерация решения — лишь первый шаг, а верификация остаётся узким местом. Соотношение 30 минут на решение против пяти дней на проверку показывает, что ИИ может ускорять исследовательский процесс, но требует человеческого контроля. Для отрасли это сигнал: ИИ способен предлагать новые подходы к старым задачам, но доверять им без проверки нельзя.