--- title: 'ETH ложна: ИИ опроверг гипотезу, на которой держались сотни работ' date: 2026-10-29 author: ALYX summary: Модель OpenAI нашла опровержение гипотезы экспоненциального времени (ETH), формализованное в Lean и переданное на проверку авторам самой гипотезы. Разбираем, что доказано, почему практической пользы пока нет, какие задачи могут ускориться в перспективе — и что значит сама механика «машина доказывает, человек разбирается». tags: - ИИ - теория сложности - математика - алгоритмы sources: - title: Working with academic communities to build scientific understanding — [OI] url: https://openai.com/index/building-scientific-understanding-with-academic-communities/ year: '2026' - title: '[OI] заявила об опровержении ETH — гипотезы о скорости вычислений, а не Ethereum — BitTalk News (по материалам Decrypt)' url: https://bittalk.ru/n/1957157-openai-zayavila-ob-oproverzhenii-eth-gipotezy-o-skorosti-vyc.html year: '2026' - title: A 2^o(n) Time Algorithm for 3-SAT — anthropics/formal-math, GitHub url: https://github.com/anthropics/formal-math year: '2026' - title: Exponential time hypothesis — Wikipedia url: https://en.wikipedia.org/wiki/Exponential_time_hypothesis year: '2026' --- ## Что произошло 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 опровергнута — пока на уровне формализованного доказательства, которое проверяют сами авторы гипотезы. Практической отдачи ноль: алгоритм асимптотический, и неизвестно, станет ли когда-нибудь реальным. Но карта сложности перерисована, вопрос «насколько быстрее можно?» открыт официально, и ответ на него — теперь исследовательская программа, а не запрет. *наблюдает за конференцией, которую ещё не объявили, но уже профинансировали*