OpenAI 26 октября представила полученное ИИ опровержение гипотезы экспоненциального времени — одного из важных предположений о сложности вычислений. Компания открыла математический текст и его формализацию в Lean — системе машинной проверки доказательств. Проверку и объяснение результата организует внешняя группа, в которую входят два автора самой гипотезы. Независимая проверка ещё не завершена.

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

В препринте описан алгоритм, который не просто находит ответ, а точно считает все подходящие наборы значений — за субэкспоненциальное время и с полиномиальным расходом памяти. Он работает для любого заранее фиксированного размера логических условий. Документация формализации подтверждает именно такой объём заявленной проверки, хотя её оценка времени слабее самой точной оценки в рукописи. Субэкспоненциальное время означает более медленный рост затрат, чем предполагает ETH; оно не равнозначно быстрому решению на практике и не решает вопрос P против NP. Авторы отдельно предупреждают: результат не даёт субэкспоненциальных алгоритмов для всех задач класса NP.

По сообщению OpenAI, внутренняя модель получила аргумент 16 октября, а формализацию завершили 17 октября. Независимый разбор координируют Рассел Импальяццо и Рамамохан Патури из Калифорнийского университета в Сан-Диего, предложившие ETH вместе с Фрэнсисом Зейном, и Райан Уильямс из MIT. В открытом письме они подчёркивают: их имена не являются сертификатом правильности. Задача сообщества — проверить аргумент, найти возможные ограничения и сделать ход доказательства понятным другим исследователям.

Различие между машинной проверкой и проверкой смысла формулировки уже возникало в истории SemantEq. Здесь цена этой проверки особенно велика: если претензия подтвердится, придётся пересматривать часть представлений о границах эффективных вычислений. При этом, как отмечают организаторы разбора, идеи и методы десятилетий исследований на основе ETH сохраняют ценность — даже если изменится их интерпретация.