OpenAI и Anthropic заявили о возможном опровержении гипотезы ETH

OpenAI опубликовала решения трёх крупных математических задач, среди которых оказалось возможное опровержение гипотезы экспоненциального времени (ETH). Вскоре Anthropic также сообщила о собственной работе с аналогичным выводом. Если доказательства подтвердятся, речь пойдёт об алгоритмах, решающих определённый класс логических задач за субэкспоненциальное время вместо ожидаемого экспоненциального.

Что утверждает гипотеза ETH

ETH сформулировали в 1999 году специалисты по теории сложности Рассел Импальяццо и Рамамохан Патури. Она относится к кругу вопросов P против NP: можно ли столь же быстро находить решения задач, как и проверять уже найденные.

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

OpenAI и Anthropic утверждают, что их модели нашли алгоритмы с субэкспоненциальным временем работы для таких задач. Это не является доказательством равенства P и NP, однако ставит под сомнение одну из важных опор интуиции о вычислительной трудности NP-задач.

Проверка доказательств и последствия

Ответ компьютерных учёных координирует профессор MIT Райан Уильямс, работающий в области вычислительной сложности. Вместе с Импальяццо и Патури он призвал заинтересованных исследователей к открытому обсуждению доказательств и норм публикации результатов, созданных при участии ИИ.

Уильямс отметил, что часть доказательства OpenAI выглядит рутинной, но в нём есть несколько необычных фрагментов, требующих совместной проверки сообщества. По его словам, результат может заставить исследователей с большим вниманием относиться к возможности P = NP, но не даёт окончательного ответа и не означает, что предложенный алгоритм предельно эффективен.

Почему затронута криптография

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

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

Что учитывать компаниям

Для бизнеса новость пока не означает, что шифрование стало небезопасным или что практические задачи резко подешевели в вычислениях. Она показывает, что результаты, полученные передовыми ИИ-моделями, могут затрагивать фундаментальные допущения. Разумный практический вывод — следить за независимой верификацией, не менять защитные механизмы на основании предварительных заявлений и оценивать последствия только после публикации и разбора доказательств.