Дмитрис Папаилиопулос, исследователь Microsoft Research и в прошлом теоретик информации, рассказал, как GPT-5.6 и Claude Fable 5 закрыли вопрос, который стоял открытым с 2001 года: можно ли решить задачу MIMO-детекции быстрым алгоритмом везде, где ее в принципе можно решить. Над этим вопросом он сам работал аспирантом в 2009-м, а теперь просто задал его двум моделям. Первое доказательство GPT выдал примерно за 30 минут. Дальше началась настоящая работа: пять дней ушло на то, чтобы превратить ответ машины в текст, который человек способен проверить построчно. «Верификация — безумное бутылочное горлышко», — подвел итог Папаилиопулос. Это соотношение — 30 минут на решение против недели на проверку — и есть главная новость.
Сама задача формулируется на пальцах. Передатчик с N антеннами отправляет N битов — цепочку из плюс и минус единиц — приемнику, у которого тоже N антенн. Эфир смешивает сигналы: каждая приемная антенна слышит не «свой» бит, а взвешенную кашу из всех N сразу, и сверху ложится случайный шум. Пропорции смешивания (матрицу канала) приемник знает — их измеряют служебными сигналами, — а шум нет. Требуется восстановить все биты до единого. Это MIMO-детекция; сама технология MIMO сидит в каждом Wi-Fi роутере и базовой станции 5G. Оптимальный по вероятности ошибки метод известен давно: перебрать все комбинации битов и выбрать ту, что лучше всего объясняет принятый сигнал. Одна беда — комбинаций 2^N, а в общем случае задача NP-трудна, что Серхио Верду доказал еще в 1989 году.
Но NP-трудность — утверждение про худший случай, про специально подобранную злодейскую матрицу. Реальный радиоканал случаен, и для случайных матриц теоретики информации к концу 2000-х выяснили точную границу возможного. Все решает отношение сигнал/шум: при SNR выше порога 2 log N полный перебор восстанавливает все биты с вероятностью, стремящейся к единице, а ниже порога вероятность восстановления стремится к нулю. Отсюда вопрос, который сообщество сформулировало в начале нулевых: дотягивается ли до этого же порога какой-нибудь быстрый, полиномиальный алгоритм? Или между «статистически возможно» и «вычислительно достижимо» зияет зазор — зона, где правильный ответ существует, но найти его за разумное время нельзя? В других задачах такие зазоры между статистикой и вычислениями действительно встречаются.
За четверть века история вопроса успела обзавестись драмой. В 2001-м Хассиби и Викало посчитали ожидаемую сложность популярного тогда Sphere Decoder и получили формулу, которая выглядела полиномиальной, — казалось, вопрос закрыт. Через четыре года Ялден и Оттерстен показали, что интерпретация неверна: при любом фиксированном SNR ожидаемая сложность сферического декодера все равно экспоненциальна. Дальше поле пробовало все подряд: полуопределенные релаксации с гарантиями лишь при высоком SNR, AMP-методы, точно описывающие ошибку на бит, но не восстановление блока, алгоритмы из арсенала статистической физики, чьи предсказания так и остались без строгих доказательств. Сам Папаилиопулос в 2010-м, в первой своей статье с Алексом Димакисом, анализировал MCMC-метод — и тоже не смог доказать главного, оценки времени перемешивания. Единственным строгим результатом за все годы осталась box relaxation: в 2020-м для нее доказали восстановление блока с порога 4 log N — и доказали, что ниже она не работает. Вдвое хуже перебора. На этом активность затухла: поле разошлось по другим темам, и вопрос завис.
Вернуться к нему Папаилиопулоса заставила волна успехов моделей на трудной математике. Замысел он описывает почти как жанр: пойти по задачам, которые преследовали тебя в аспирантуре, и «навести на них Звезду Смерти». Из всех кандидатов он выбрал самый амбициозный и при этом чисто сформулированный вопрос — и заранее понимал, в чем будет засада. Даже если модель выдаст полный ответ, им нельзя поделиться, пока не проверишь сам: «во-первых, не хочу опозориться, если окажется неверно, а во-вторых, делиться — главная причина, по которой мы вообще задаем вопросы и занимаемся наукой».
Обе модели ответили одинаково. GPT-5.6 и Claude Fable 5 заявили: зазора нет, полиномиальный алгоритм работает с того же порога 2 log N, что и перебор, — и предъявили доказательства для разных алгоритмов. Вариант GPT строился на AMP, семействе методов, чьи анализы Папаилиопулос, по собственному признанию, «ненавидит всей душой», потому что не понимает. Fable предложил то, что автору сразу понравилось: грубая линейная прикидка с округлением до знаков, а затем жадные перевороты битов — алгоритм, давно известный и реально применявшийся на практике. Дальше сюжетный твист: по вердикту GPT, доказательство Fable было «по большей части неверным, но спасаемым». Папаилиопулос решил оставить алгоритм Fable — и попросил GPT починить его доказательство. Тот справился. Алгоритм — от одной модели, работающее доказательство — плод их соавторства.
Но починенное доказательство оказалось нечитаемым: «стена нотации, переменные, указывающие на переменные, указывающие на отношения переменных, определяющих другие переменные, экзотическая матричная аналитика, штуки в духе Марченко — Пастура, от которых у меня крапивница». И следующие четыре-пять дней Папаилиопулос гонял обе модели по кругу, требуя для каждого блока доказательства «тупейший возможный набор шагов» и явно разрешая ухудшать константы и оценки — лишь бы порог 2 log N устоял, а шаги мог проверить, по его собственной формулировке, «старый динозавр, неспособный долго удерживать внимание». Модели упрощали аргументы друг друга, автор отбраковывал все, за чем не мог уследить, и постил скриншоты собственного нытья в чатах — самый честный из них, с опечатками отчаяния: «как мне это читать, я прочитал лемму и забыл, как она связана с остальным… я сейчас заплачу». От формальной верификации в Lean он отказался: она, по его словам, лишь сдвигает проверку на другой уровень абстракции. В итоге получился длинный, но элементарный текст, который автор проверил строчку за строчкой.
Устроено решение действительно просто. Шаг первый: забыть на минуту, что биты дискретны, решить задачу как обычную систему уравнений с поправкой на шум (это и есть LMMSE — по сути умное обращение матрицы) и округлить дробные ответы до знаков. Доказывается, что такая прикидка ошибается лишь в исчезающе малой доле битов. Шаг второй: жадно переворачивать тот бит, который сильнее всего уменьшает невязку — расстояние между принятым сигналом и тем, что дала бы текущая догадка, — пока есть что улучшать. Обычно жадные алгоритмы гибнут в локальных ямах — точках, где любой одиночный шаг делает хуже, хотя до правильного ответа далеко, — но здесь доказано, что ландшафт задачи вблизи истины устроен благосклонно: в любой неправильной точке найдется переворот с гарантированным выигрышем, значит застрять негде; убежать далеко тоже нельзя — вокруг стартовой точки стоит «ценовой барьер» из состояний, которые дороже нее, а путь, идущий только вниз по невязке, через такой барьер не переваливает. Каждый шаг съедает гарантированный кусок ограниченного запаса — отсюда оценка примерно в N log N шагов, и остановиться алгоритму негде, кроме как в правильном ответе. Примечательно, что во всем этом нет ни одной новой идеи: ни неравенств, ни техник, ни объектов, которых не существовало бы в 2010 году.
Теперь о том, что стоит держать в голове скептику. Статья пока не прошла ничьей проверки, кроме авторской: она приложена к посту в X, на arXiv Папаилиопулос только обещает ее выложить, в рецензируемое издание может и не подавать — и открыто просит читателей искать ошибки. Прецеденты, когда красивое ИИ-доказательство разваливалось при внешней проверке, уже были. Заявки на «решение MIMO» тоже случались и раньше — но с численными экспериментами и эвристическими аргументами вместо строгого доказательства на пороге. И отдельно про практику, честно: вашему роутеру этот результат не поможет. Модель идеализирована — простейшие сигналы из ±1 вместо реальных созвездий модуляции, гауссовский канал, никакого помехоустойчивого кодирования поверх; инженеры десятилетиями использовали похожие эвристики без всяких теорем, просто глядя на графики ошибок, а исследовательское поле давно ушло вперед. Закрыт вопрос теории, а не проблема индустрии — сам автор оценивает результат как «святой грааль» образца 2010 года, за который тогда дали бы премию за лучшую статью на профильных конференциях и собеседования в MIT и Стэнфорде.
Под конец Папаилиопулос предлагает мысленный эксперимент. Возьмите ту же модель с теми же вычислительными затратами на обучение с подкреплением, но с претрейном на данных только до 2005 года — решила бы она задачу? Инструменты в основном существовали и тогда, но «тяга» модели к правильному набору идей — отражение того, как часто сообщество применяло метод в похожих контекстах, а этот коллективный инстинкт дозрел позже. Если так, то модели — не оракулы математической истины, а «дистилляция наших накопленных инстинктов, дополнительно заостренная обучением с подкреплением». И тогда закрытая задача — это не только победа машины, но и запоздалый дивиденд с работы всего сообщества, которое разошлось, не успев его получить.
Отсюда и главный вывод, который шире одной задачи. Существует целый класс проблем, брошенных не потому, что они неприступны, а потому, что люди постепенно перестали ими заниматься: сообщества распались, мода ушла, вопросы остались стоять «тихо и беззащитно, в заброшенном углу вселенной литературы». Для их решения, как выяснилось, не нужна новая математика — нужен тот, кто готов потратить подписку за 200 долларов и неделю жизни на сборку и проверку известных идей. Алекс Димакис — соавтор той самой статьи 2010 года, а вскоре после нее и научный руководитель Папаилиопулоса — в ответном комментарии сформулировал, что это меняет в самой профессии: раз сложность доказательства перестала быть узким местом, им становятся проверка корректности, элементарность шагов и умение рассказать историю — а времена, когда в престижный теоретический журнал помогала пройти демонстрация модного тяжелого аппарата, заканчиваются.
P.S. Поддержать меня можно подпиской на канал «сбежавшая нейросеть», где я рассказываю про ИИ с творческой стороны.
ссылка на оригинал статьи https://habr.com/ru/articles/1068458/