Хакатон AI‑контента · 28–29 ноябряУчаствовать

Опровержение ETH: что заявили OpenAI и Anthropic

Опровержение ETH: что заявили OpenAI и Anthropic

Две конкурирующие ИИ-лаборатории утверждают, что их модели нашли алгоритмы, опровергающие гипотезу экспоненциального времени (Exponential Time Hypothesis, ETH). Эта гипотеза десятилетиями служила фундаментом для доказательств того, насколько трудны многие вычислительные задачи. Если результаты подтвердятся в полном объёме, теории алгоритмов придётся пересмотреть значительную часть привычных оценок сложности.

OpenAI и Anthropic представили препринты и формализации в Lean ещё в конце октября 2026 года. Новым поводом для обсуждения стало сообщение Калифорнийского университета в Сан-Диего от 19 ноября: ведущие специалисты, включая авторов самой гипотезы, организуют независимую проверку утверждений. На момент публикации это предмет активного научного изучения, а не завершённая общепринятая рецензия.

Что такое ETH и почему она важна

Представим задачу с несколькими логическими условиями: каждое условие требует, чтобы хотя бы одно из трёх утверждений было истинным. Нужно найти значения переменных, при которых одновременно выполняются все условия. Это задача 3-SAT, один из классических примеров NP-полной проблемы.

Простой способ решения - перебрать все сочетания значений. Для n логических переменных таких сочетаний 2^n. При увеличении числа переменных даже небольшие изменения n резко увеличивают объём перебора.

Гипотеза ETH утверждает, что для 3-SAT в худшем случае невозможно получить субэкспоненциальный алгоритм: время работы неизбежно имеет экспоненциальную зависимость от n, условно 2^(Ω(n)). Гипотезу сформулировали Рассел Импальяццо, Мохан Патури и Фрэнсис Зейн на рубеже 1990-х и 2000-х годов.

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

Что означает предполагаемое опровержение ETH

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

Что представила OpenAI

Согласно опубликованному сообщению, исследовательская система OpenAI получила доказательство на естественном языке 16 октября 2026 года, а на следующий день компания формализовала результат в Lean. Позднее были опубликованы текст работы и код формализации.

Авторы заявляют алгоритм для задач k-SAT, способный работать за субэкспоненциальное время при фиксированном k. Формально это означает время вида 2^(o(n)) с дополнительными полиномиальными множителями. Такой результат противоречил бы ETH, которая запрещает алгоритм столь низкой асимптотической сложности для 3-SAT.

Здесь есть два важных ограничения. Во-первых, математическая оценка касается асимптотического роста времени при очень больших входных данных, а не гарантированного ускорения конкретного SAT-решателя уже сегодня. Во-вторых, проверка формального доказательства подтверждает именно записанную математическую теорему; соответствие формализации всей заявленной интерпретации тоже должно быть изучено.

Что представила Anthropic

Вскоре Anthropic опубликовала собственную работу «A 2^o(n) Time Algorithm for 3-SAT», приписываемую внутренней исследовательской модели Claude. В описании исследования говорится, что модель работала автономно и сгенерировала около 14 млн выходных токенов для поиска решения.

Anthropic также предоставила проект Lean с основной теоремой и средствами проверки. В репозитории результат сформулирован как существование детерминированного субэкспоненциального алгоритма для 3-SAT. Материалы обеих лабораторий доступны для повторного запуска и независимого анализа.

Они относятся к одной фундаментальной проблеме, но различаются техническими конструкциями и формой доказательства. Публикации обеих сторон сами по себе ещё не заменяют экспертного анализа доказательств.

Что уже проверено и что остаётся открытым

Часть сообщества начала воспроизводить формальные проверки. На площадке ETH: Community Examination and Discussion опубликованы независимые попытки повторного запуска проектов Lean, комментарии к формулировкам теорем и материалы, объясняющие сложные части доказательств. Некоторые участники подтверждают, что предоставленные формальные разработки проходят проверку относительно собственных утверждений.

Но нужно различать три уровня проверки: воспроизводится ли код в Lean; доказывает ли код именно математическое утверждение из статьи; верна ли полная интерпретация этого утверждения применительно к классической ETH. На каждом уровне могут возникать отдельные вопросы о моделях вычислений, кодировках входных данных и времени преобразований.

Организацию независимого обсуждения взяли на себя Импальяццо и Патури из UC San Diego, а также Райан Уильямс из MIT. В заявлении исследователей прямо сказано: участие организаторов не следует считать подтверждением корректности результата. Они планируют открытое изучение работ и научные встречи.

Специалист по теории сложности Лэнс Фортноу в своём блоге выразил оптимизм относительно результата, одновременно отметив, что лично не проверил доказательство. Он также подчеркнул важную логическую деталь: если условная гипотеза оказывается ложной, выводы, ранее следовавшие из неё, не обязательно становятся ложными. Просто прежнее обоснование уже нельзя применять в том же виде.

Означает ли это решение P против NP

Нет. Даже корректный алгоритм с временем 2^(o(n)) может оставаться намного медленнее любого полиномиального алгоритма. Поэтому из опровержения ETH не следует равенство P и NP и не появляется универсальный быстрый способ решать все NP-полные задачи.

Нельзя также делать вывод, что в ближайшее время будут взломаны используемые в интернете криптосистемы. Практические последствия зависят от конкретных алгоритмов, их констант, размеров задач и возможных преобразований других проблем в 3-SAT.

Потенциал результата огромен для теории. Он может открыть путь к новым алгоритмическим оценкам и заставить пересмотреть сотни исследований, использующих ETH как предпосылку. Но путь от асимптотической теоремы до ускорения реального программного обеспечения может быть очень долгим.

Почему эта история особенно важна для ИИ

В центре внимания оказывается не соревнование брендов, а новый порядок научной работы. ИИ-системы предлагают доказательства такой сложности, что для их анализа требуются коллективные усилия специалистов, формальные проверяющие системы и независимые объяснения.

Если результат выдержит проверку, это станет значительным достижением ИИ в фундаментальной математике. Если обнаружатся пробелы, сама процедура публичного анализа всё равно покажет, как научному сообществу проверять всё более масштабные результаты, полученные с помощью моделей. Научное открытие приобретает ценность тогда, когда его можно воспроизвести, понять и независимо подтвердить.

Источники