Задача, которая ждала четверть века

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

Первый вариант доказательства GPT выдал примерно за 30 минут. Дальше началась настоящая работа: пять дней ушло на то, чтобы превратить ответ машины в текст, проверяемый построчно. «Верификация — безумное бутылочное горлышко», — подвёл итог автор.

Что такое MIMO-детекция

Передатчик с N антеннами отправляет N битов — цепочку из плюс и минус единиц — приёмнику с таким же числом антенн. Эфир смешивает сигналы: каждая антенна слышит взвешенную кашу из всех N сразу, поверх которой ложится случайный шум. Нужно восстановить все биты до единого. MIMO живёт в каждом Wi-Fi-роутере и базовой станции 5G.

Оптимальный метод известен давно — полный перебор всех комбинаций, но их 2^N, и в общем случае задача NP-трудна. Вопрос, зависший с начала нулевых: дотягивается ли до теоретического порога быстрый алгоритм, или между «статистически возможно» и «вычислительно достижимо» зияет зазор?

Как модели справились

Обе модели ответили одинаково: зазора нет, полиномиальный алгоритм работает с того же порога, что и перебор. GPT предложил доказательство на базе AMP, а Fable — линейную прикидку с округлением и жадными переворотами битов. По вердикту GPT, доказательство Fable было «по большей части неверным, но спасаемым» — автор попросил GPT починить его. Так алгоритм достался одной модели, а доказательство стало плодом их соавторства.

Решение устроено элегантно: сначала задача решается как обычная система уравнений, затем жадными переворотами битов невязка сводится к нулю. Доказано, что застрять в локальной яме негде.

Что это значит на практике

  • Статья пока прошла только авторскую проверку — автор открыто просит читателей искать ошибки.
  • Роутерам результат не поможет: модель идеализирована, а инженеры давно используют похожие эвристики.
  • Закрыт вопрос теории, а не проблема индустрии — автор называет результат «святым граалем» 2010 года.

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