ETH опровергнута? Что заявили OpenAI и Anthropic

26 октября OpenAI, а через несколько часов Anthropic выложили два независимых опровержения гипотезы экспоненциального времени (ETH) — 25-летнего предположения о сложности задачи 3-SAT. Обе работы найдены внутренними моделями 16 октября и формализованы на Lean. Это препринты: проверку организуют сами авторы гипотезы, и они подчёркивают, что их участие — не подтверждение.

Разберём, что такое ETH, что именно заявлено, что проверила машина, а что ещё нет, и почему радоваться за решатели SAT пока рано.

Что произошло 26–27 октября

OpenAI 26 октября опубликовала запись о трёх результатах своих моделей: в гармоническом анализе, теории сложности и квантовой теории поля. Второй называется прямо — «Гипотеза экспоненциального времени ложна». Вместе с записью компания выложила на GitHub текст доказательства и формализацию на Lean.

Утром 27 октября по Москве в открытом репозитории Anthropic появилась статья «Алгоритм для 3-SAT за время 2 в степени o(n)». Автором указан Claude, статья датирована 26 октября. В разделе о происхождении сказано, что ядро алгоритма нашла внутренняя исследовательская модель Claude 16 октября, без участия человека, потратив 14 миллионов токенов вывода. Там же есть ссылка на работу OpenAI: модель другой компании «независимо и одновременно» заявляет похожий результат.

Что ещё OpenAI объявила в тот же день

ETH — один из трёх результатов в записи OpenAI, и способ их выпуска заметно отличается.

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

Физический результат — строгое доказательство существования квантовой хромодинамики, а попутно и чистой теории Янга — Миллса, которая входит в одну из задач тысячелетия Института Клэя. Модели получили его ещё в сентябре, но выпуск отложили до окончания формализации на Lean. Его разбирает группа во главе с нобелевским лауреатом Дэвидом Гроссом, и материалы она пока придерживает.

Для ETH выбран средний путь: внешняя группа объясняет результат, а исходники сразу открыты всем. OpenAI пишет, что не претендует на академическое признание за открытия своих моделей, а участники групп работают независимо и не говорят от имени компании.

Что такое гипотеза экспоненциального времени простыми словами

ETH — утверждение о том, что одну конкретную трудную задачу нельзя решить существенно быстрее перебора.

Задача называется 3-SAT. Есть n переменных «да/нет» и набор условий, каждое из которых связывает не больше трёх переменных через «или». Нужно понять, можно ли выставить переменные так, чтобы выполнились все условия. Очевидный способ — перебрать все 2 в степени n вариантов. При ста переменных это уже непосильно.

С 1980-х годов алгоритмы улучшали основание степени. По данным статьи Anthropic, прежний рекорд для детерминированных алгоритмов — 1,328 в степени n, для вероятностных — 1,308 в степени n. Время оставалось экспоненциальным.

ETH, которую в статье 2001 года сформулировали Рассел Импальяццо и Рамамохан Патури, говорит: так будет всегда. Существует константа δ больше нуля, при которой 3-SAT нельзя решить за 2 в степени δn. Опровергнуть её — значит показать алгоритм, который быстрее 2 в степени δn при любом сколь угодно малом δ.

Что именно заявлено в двух работах

Оба алгоритма решают более трудную задачу, чем 3-SAT: не просто находят ответ «да/нет», а точно считают число выполняющих наборов для формул с k переменными в условии.

Время в обоих случаях субэкспоненциальное: √log n в знаменателе растёт с n, и показатель отстаёт от любого δn. Anthropic в своей статье называет результат OpenAI похожим и полученным независимо.

Значит ли это, что P равно NP

Нет. Субэкспоненциальное время — всё ещё сверхполиномиальное: алгоритм медленнее любого n в фиксированной степени. Вопрос P против NP спрашивает именно про полиномиальное время, и он остаётся открытым.

Anthropic пишет об этом во введении: результат не касается P против NP напрямую. Заголовки «ИИ решил задачу тысячелетия» к этой новости неприменимы.

Станут ли решатели SAT быстрее на практике

Пока нет оснований так считать. Anthropic сама оценивает предел: для формул с 5n условиями её граница лучше перебора только при n больше 10 в степени 10 000. Перебор непрактичен уже при ста переменных, так что, по словам авторов, результат ничего не говорит о решении формул на практике.

Райан Уильямс из MIT, отвечая на вопрос о практике, написал, что при нынешней скорости прогресса серьёзный сдвиг в практическом решении SAT за год правдоподобен, а может и не случиться: «я правда не знаю». Это честная позиция, и её стоит держать в голове, читая громкие пересказы.

Что проверил Lean, а что нет

Lean — язык, в котором доказательство записывается так, что каждый шаг проверяет программа. Если файл собрался, логических дыр в нём нет.

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

У OpenAI та же картина видна в описании формализации: Lean доказывает границу с (log log n) в квадрате, а статья заявляет более сильную. Для опровержения ETH хватает и слабой, но читать «проверено на Lean» как «проверено всё» нельзя.

Кто проверяет и на какой стадии признание

Стадия — заявлено и выложено для проверки. Рецензированной публикации нет ни у одной из компаний.

OpenAI попросила проверить свой результат группу во главе с Расселом Импальяццо и Рамамоханом Патури из Калифорнийского университета в Сан-Диего и Райаном Уильямсом из MIT. Первые двое — авторы самой гипотезы. В открытом письме коллегам группа пишет: «Наше участие не следует считать подтверждением». Результат такого масштаба требует тщательной независимой проверки.

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

Почему важно, что результатов два

Два независимых опровержения одного утверждения, найденные разными моделями в один день, — сильный сигнал, но не доказательство правоты. Если обе работы опираются на общую ошибку в понимании, совпадение её не исправит.

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

Что меняется для работ, опирающихся на ETH

ETH — стандартное допущение в доказательствах трудности: «если ETH верна, задачу X нельзя решить быстрее Y». OpenAI пишет о сотнях таких работ в теории графов, вычислительной биологии, базах данных и геометрии. В статье Anthropic названо больше 800 работ, где хотя бы один результат доказан только при ETH или более сильном предположении.

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

Что это говорит о моделях, доступных через API

Обе компании называют авторов результата внутренними исследовательскими моделями. В публичном доступе их нет.

Anthropic в README делает одно утверждение о публичной модели: Claude Opus 5.5 на высоком уровне рассуждений может по сжатому описанию идеи заново вывести более слабую версию — 3-SAT за 2 в степени δn для любого δ. Это заявление вендора, мы его не проверяли. Об уровнях рассуждения — в материале reasoning effort.

Публичные модели этих вендоров доступны в каталоге KeyDealer по одному ключу с оплатой в рублях: Claude Opus 5.5 — 60 ₽ за миллион токенов, Claude Sonnet 5 — 30 ₽, GPT-6.1 Sol — 28 ₽, GPT-6 Astra — 55 ₽. Это доступ к моделям, а не обещание научных открытий.

Сравнивать их на своих задачах стоит по стоимости решённой задачи, а не по новостям: как это делать, разобрано в материале как сравнивать модели. Что изменилось в самой Opus 5.5 — в материале Claude Opus 5.5: что ломается при переходе, про модель OpenAI — GPT-6.1 Sol: цена и бенчмарки.

Чего мы не утверждаем

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

Мы не утверждаем, что публичные модели способны на такие результаты. Открытия сделаны внутренними моделями, а заявление о повторении на Opus 5.5 принадлежит вендору.

Мы не оцениваем математику по существу. Мы пересказываем то, что написано в статьях, репозиториях и письме проверяющих, а не проверяем доказательства сами.

Что держать в голове

Первое. Стадия новости — препринты с формализацией на Lean, без рецензирования. Проверку ведут авторы гипотезы, и они сами просят не считать их участие подтверждением.

Второе. Даже если всё верно, P против NP не решён, а практической пользы для решателей SAT авторы пока не видят: выигрыш появляется на астрономических размерах.

Третье. Новость важна как сигнал о том, на что способны модели в исследованиях, но пользоваться можно только публичными версиями. Что мы за проект — на странице о проекте, ключ заводится на keydealer.ru/login.