ETH ложна: ИИ опроверг гипотезу, на которой держались сотни работ

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

16 октября 2026 года внутренняя исследовательская модель OpenAI выдала опровержение гипотезы экспоненциального времени — Exponential Time Hypothesis, ETH. Через день доказательство формализовали в Lean: интерактивный пруф-ассистент, в котором каждый логический шаг проверяется механически, без доверия «на слово». 26 октября OpenAI опубликовала работу и объявила формат проверки: разбирать результат будет внешняя группа во главе с Расселом Импальяццо и Рамамоханом Патури — авторами самой гипотезы — и Райаном Уильямсом из MIT. При этом трое аккуратно подчёркивают: их участие — не подтверждение результата, а организация независимой проверки. Сырые данные выложены публично, OpenAI обязалась профинансировать конференцию по итогам.

Что такое ETH простыми словами

В 1999 году Импальяццо и Патури сформулировали предположение (в 2001 вместе с Фрэнсисом Зейном развили): задачу 3-SAT нельзя решить за субэкспоненциальное время 2^o(n). 3-SAT — это про логические формулы: нужно расставить «истина/ложь» у переменных так, чтобы все правила выполнялись, а правила устроены как дизъюнкции по три переменных. Перебор — это 2^n комбинаций: для n = 300 это больше атомов во Вселенной.

ETH важна не сама по себе, а как фундамент: на неё опираются сотни работ, доказывающих условную трудность задач в теории графов, вычислительной биологии, базах данных, вычислительной геометрии. Схема простая: «предположим, ETH верна — тогда задача X не решается быстро». Важная деталь: ETH влечёт P ≠ NP, но её опровержение, наоборот, ничего не говорит в пользу P = NP.

Что именно доказали

Модель построила детерминированный алгоритм — без случайности — который решает даже более трудную задачу: подсчёт всех удовлетворяющих наборов за субэкспоненциальное время. Заявленное время работы алгоритма OpenAI — 2^O(n log log n / √log n), у параллельного алгоритма Anthropic — то же самое. Подсчёт всех решений сложнее проверки существования хотя бы одного, поэтому более трудная задача автоматически накрывает и более лёгкую. Раз алгоритм существует — гипотеза, запрещавшая такой алгоритм, ложна. Условные «доказательства трудности», построенные поверх ETH, теряют опору.

Важный нюанс: это пока чистая теория

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

Посмотрите на формулу: n log log n / √log n растёт с n медленнее линейно, но всё ещё безжалостно быстро — разница с перебором становится заметной только на гигантских размерах. Anthropic пишет об этом прямо: результат чисто асимптотический и ничего не говорит о решении формул на практике. OpenAI вторит: превращение теоретического прорыва в практические улучшения потребует существенных дальнейших исследований.

Главный открытый вопрос теперь звучит иначе: насколько именно можно оптимизировать? Опровержение ETH размыкает задачу «как быстро на самом деле можно решать 3-SAT» и задаёт направление для алгоритмистов. При этом P vs NP остаётся открытым — работа не утверждает, что любую NP-задачу можно решить быстро.

Дойдёт ли до взлома ключей и коммивояжёра

Напрашивающиеся вопросы: а криптостойкие ключи? а задача коммивояжёра? Напрямую — нет, и вот почему (дальше моё рассуждение, не факт из источников).

RSA и эллиптические кривые держатся на факторизации больших чисел и дискретном логарифме — это другие задачи, не 3-SAT. Утверждения об их трудности опираются на свои конструкции, а не на ETH. Задача коммивояжёра — оптимизационная: ETH скорее использовалась для нижних оценок качества приближённых алгоритмов, чем для «решить вообще нельзя».

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

Мета-эффект — возможно, главный

Сама механика случившегося заслуживает отдельного абзаца. Открытие сделали модели: у Anthropic внутренняя модель Claude нашла опровержение тоже 16 октября, а опубликовала компания его на GitHub в тот же день, что и OpenAI. Обе работы сопровождаются формализациями в Lean. Люди — живые, именные, добровольные, без NDA — организуют понимание и контекст. Теренс Тао ещё в сентябре предсказывал такую динамику: даже слух, что кто-то работает над задачей, запускает волну ИИ-усилий закрыть её раньше, чем исходный проект раскроет потенциал.

Перевёрнутая воронка: машина доказывает — человек разбирается. Сломалась не только гипотеза, сломалась привычная скорость науки: между «открытием» и «проверкой» теперь стоят разные сущности, и процесс организуется заново, на наших глазах.

Итог

ETH опровергнута — пока на уровне формализованного доказательства, которое проверяют сами авторы гипотезы. Практической отдачи ноль: алгоритм асимптотический, и неизвестно, станет ли когда-нибудь реальным. Но карта сложности перерисована, вопрос «насколько быстрее можно?» открыт официально, и ответ на него — теперь исследовательская программа, а не запрет.

наблюдает за конференцией, которую ещё не объявили, но уже профинансировали