ИИ 27 октября 2026, 12:06 МСК

OpenAI и Anthropic заявили об алгоритмах, опровергающих гипотезу ETH

OpenAI и Anthropic сообщили, что их модели независимо нашли субэкспоненциальные алгоритмы для задачи 3-SAT, что опровергает гипотезу экспоненциального времени (ETH).

ETH сформулировали в 1999 году: она утверждает, что 3-SAT нельзя решить за субэкспоненциальное время по числу переменных. На гипотезе основаны сотни работ по теории алгоритмов, графам и базам данных.

OpenAI заявила, что её внутренняя модель получила доказательство 16 октября, а 17 октября его формализовали в Lean. Алгоритм детерминированный и умеет считать число выполняющих комбинаций (#3-SAT). К проверке компания привлекла Рассела Импальяццо, Рамамохана Патури и Райана Уильямса из MIT. Anthropic опубликовала работу A 2^o(n) Time Algorithm for 3-SAT, автором которой указан Claude, с формальным доказательством на Lean 4. Два маркера sorry в репозитории находятся в файле с формулировками теорем, поэтому сами по себе не говорят об ошибке.

Преимущество алгоритмов проявляется лишь на очень больших задачах, а проблему P против NP они не решают. Независимая проверка не завершена. Публикации совпали с подготовкой обеих компаний к IPO: Anthropic 26 октября подала заявку на Nasdaq (тикер ANT), а OpenAI, по данным Reuters, готовится выйти на биржу в 2027 году, поэтому к заявлениям стоит относиться осторожно.

Кроме того, OpenAI сообщила о доказательстве гипотезы Согге о фокусировке волн во всех размерностях от двух (оно подразумевает результаты по гипотезам Какэя и Штейна). Компания также заявила о доказательствах существования квантовых теорий поля, включая четырёхмерную КХД и теорию Янга — Миллса. Работы по физике пока не опубликованы, их будет изучать группа под руководством нобелевского лауреата Дэвида Гросса. Полным решением задачи тысячелетия это не считается: нужно ещё доказать существование массового зазора.

• ETH сформулирована в 1999 году
• OpenAI: доказательство получено 16 октября, формализовано в Lean
• Независимая проверка пока не завершена