26 октября 2026 года OpenAI и Anthropic в один день выложили в открытые репозитории препринты с машинно-проверяемыми в Lean доказательствами субэкспоненциальных алгоритмов для SAT-задач, что опровергает ETH — гипотезу Импальяццо и Патури 1999 года о том, что 3-SAT не решается быстрее, чем за c^n. Внутренняя корректность доказательств проверяется механически, но открытым остаётся вопрос, отрицает ли формальная теорема именно ETH, и его уже изучает рабочая группа во главе с MIT-профессором Райаном Уильямсом. Для продакшена, криптографии и SAT-солверов пока не меняется ничего, зато впервые две конкурирующие frontier-лаборатории одновременно опубликовали одинаково громкую фундаментальную заявку с проверяемыми артефактами.

image

Что произошло

OpenAI 26 октября 2026 года выложила в открытый репозиторий openai/math 67-страничный препринт «The Exponential Time Hypothesis Is False», датированный 25 октября. Внутри — полное машинно-проверяемое доказательство в Lean: внутренняя модель компании, по её заявлению, нашла детерминированный алгоритм, который считает число выполняющих назначений k-CNF-формулы при k >= 2 за время (n+m)^{O_k(1)} * 2^{n/(log n)^{1/2+o(1)}} в полиномиальной памяти. В тот же день Anthropic опубликовала в репозитории anthropics/formal-math 49-страничную статью «A 2^o(n) Time Algorithm for 3-SAT»: внутренняя исследовательская Claude-модель дала детерминированный алгоритм для #3-SAT за 2^{O(n log log n / sqrt(log n))}, формализованный в Lean 4 против Mathlib. Контраст с предшествующим рекордом разительный: лучшие известные алгоритмы для 3-SAT имели константные основания степени, около 1.328^n у детерминированного и 1.308^n у рандомизированного, тогда как новые границы впервые субэкспоненциальны. При этом OpenAI признаёт, что доказанная в Lean оценка слабее заявленной, а ключевые процессные детали Anthropic — около 14 млн токенов вывода и работа без участия человека в поиске алгоритма — остаются самосообщением команды. Пост на Hacker News на момент сбора данных имел 1 балл и 0 комментариев, а пресс-цикл прошёл через TechCrunch 27 октября и The New York Times 6 ноября.

Контекст

ETH — Exponential Time Hypothesis — сформулирована в 1999 году Расселом Импальяццо и Рамамурти Патури и утверждает, что 3-SAT не решается быстрее, чем за c^n. На этой гипотезе построены сотни работ о жёсткости задач, включая Clique, Vertex Cover и Independent Set, поэтому её называют «рабочей лошадкой» теории сложности: если опровержение устоит, пересматривать придётся целый пласт fine-grained-сложности, а не одну теорему. Вторая часть контекста — методологическая. Главное отличие от привычных новостей про «ИИ совершил прорыв» в том, что обе статьи содержат формализацию в Lean, у Anthropic — в Lean 4 против Mathlib, поэтому внутренняя корректность выкладок проверяется механической программой, а не доверием к лаборатории. Узкое место при этом смещается в фидельность формулировки: вопрос уже не в том, верна ли выкладка, а в том, отрицает ли доказанная теорема именно ETH. Третья часть — защита от типичной ошибки трактовок: опровержение ETH не равно P = NP. Обе заявленные оценки, 2^{n/(log n)^{1/2+o(1)}} у OpenAI и 2^{O(n log log n / sqrt(log n))} у Anthropic, остаются суперполиномиальными, границы двух команд различаются младшими факторами вроде log log n и o(1)-термов, и, по данным источников, ни одно из доказательств не утверждает P = NP.

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

Непосредственно в продакшене сейчас не меняется ничего: нет API, нет реализации, нет замеров реального времени выполнения, изменений в инференсе, латентности и стоимости тоже нет. Для SAT-солверов практического выигрыша нет, преимущество над полным перебором проявляется только на входах в десятки тысяч переменных, а криптографическим системам, по заявлениям самих участников, ничего не угрожает: OpenAI выразила «разумную уверенность», что новые алгоритмы не ломают текущие системы. Реальное воздействие происходит внутри науки: сообщество теории сложности мобилизовано на верификацию, MIT-профессор Райан Уильямс организовал рабочую группу и воркшопы с авторами исходной гипотезы Импальяццо и Патури, чтобы проверить, соответствуют ли формальные утверждения в Lean самой ETH. При подтверждении заявки пересмотра потребуют сотни результатов о жёсткости, построенных на ETH, включая Clique, Vertex Cover и Independent Set. Для инженерных и продуктовых команд сигнал двоякий. Первое: неожиданно критическим ресурсом обеих frontier-лабораторий оказалась связка Lean и Mathlib, и это прямой индикатор спроса на такие компетенции. Второе: подтверждён рабочий паттерн, при котором автономная модель работает часами над задачей, а финальным артефактом становится объект, проверяемый детерминированным верификатором — Lean, Mathlib, компилятором или раннером тестов; пайплайны «модель предлагает — верификатор проверяет» имеет смысл закладывать уже сейчас, сохраняя артефакты всех попыток, а не только витринные. Третье: налицо новая экономика исследования, где две конкурирующие лаборатории в один день независимо пришли к одной фундаментальной заявке, а единственное разумное действие для команды сегодня — прочитать препринты в openai/math и anthropics/formal-math и завести внутренний трекер выводов рабочей группы Уильямса.

Почему это важно для пользователей

Для читателя значима сама форма публикации: впервые две frontier-лаборатории независимо пришли к одному и тому же фундаментальному опровержению и выложили его с машинно-проверяемыми доказательствами, а не просто рассказом о том, как «модель рассуждала». Препринты открыты в репозиториях openai/math и anthropics/formal-math, и внутреннюю корректность доказательств любой желающий может перепроверить сам, запустив Lean, не полагаясь на пресс-релизы. Немедленной пользы ждать не стоит: никакие инструменты не выходят, сервисы не ускоряются, пароли менять не нужно, а криптография, по заявлениям авторов, не взломана. Дальше стоит следить за тремя вещами: за выводами рабочей группы Уильямса о том, отрицает ли формальная теорема именно ETH; за разбором «alien-looking parts», то есть непривычно выглядящих фрагментов доказательства; за тем, выдержит ли оценка 2^{n/(log n)^{1/2+o(1)}} перенос полиномиальными редукциями к другим NP-задачам. И запасной ориентир на случай громких пересказов: версии, что «ИИ решил проблему P vs NP», — фактическая ошибка, обе заявленные оценки остаются суперполиномиальными.

Что пока неизвестно / ограничения

Это заявки лабораторий, которые не прошли peer review, поэтому считать опровержение ETH состоявшимся фактом рано. OpenAI прямо признаёт, что доказанная в Lean оценка слабее заявленной в заголовке, так что точная формулировка результата может сдвинуться при разборе. Процессные детали Anthropic — около 14 млн токенов вывода и поиск алгоритма без участия человека — самосообщения без внешней проверки. В открытой истории есть только успешные витринные артефакты: нет статистики попыток, неудачных прогонов и степени неявного управления поиском, из-за чего связку «модель предлагает — Lean проверяет» нельзя считать надёжно валидированным шаблоном. Ключевая неизвестная — фидельность формализации, то есть действительно ли доказанная в Lean теорема отрицает именно ETH; именно это проверяет рабочая группа Уильямса, и её выводов пока нет. Наконец, отсутствуют реализация и независимые измерения производительности: неизвестно, на каких входах новые алгоритмы фактически обгоняют детерминированный рекорд 1.328^n и переносится ли открытая оценка полиномиальными редукциями к другим NP-задачам.

Источники

Автор

Look at AI, редакция