OpenAI и Anthropic сообщили, что их исследовательские модели нашли алгоритмы, опровергающие гипотезу экспоненциального времени — ETH. На этом предположении построены многочисленные оценки сложности вычислительных задач. Если результат выдержит проверку, исследователям придётся пересмотреть часть представлений о том, какие алгоритмы вообще возможны.
Масштаб последствий зависит от того, какое ускорение обещают новые алгоритмы. Для этого нужно разобраться в связи ETH с проблемой P против NP.
Что опубликовали лаборатории
26 октября 2026 года OpenAI объявила о результатах в трёх областях: математическом анализе, теории вычислительной сложности и квантовой теории поля. Заявление об ETH относится ко второй. Компания выложила текст доказательства и его формализацию в Lean — системе проверки математических доказательств.
Вскоре собственные материалы представила Anthropic. Компания приписывает результат внутренней исследовательской модели Claude. Заявленный алгоритм решает задачу 3-SAT за субэкспоненциальное время. Он также должен подсчитывать число удовлетворяющих формуле наборов значений.
За внешнее изучение результата OpenAI взялись Райан Уильямс из MIT, Рассел Импальяццо и Рамамохан Патури из Калифорнийского университета в Сан-Диего. В открытом письме исследователи подчеркнули: их участие не означает, что заявленное опровержение уже получило научное подтверждение.
Какую границу устанавливает ETH
ETH касается задачи выполнимости булевых формул. В варианте 3-SAT формула состоит из условий, соединённых оператором «И». Каждое условие содержит до трёх переменных или их отрицаний, связанных через «ИЛИ». Нужно подобрать значения «истина» и «ложь», при которых вся формула окажется истинной.
Простой пример:
(x ИЛИ y ИЛИ НЕ z) И (НЕ x ИЛИ z ИЛИ w).
Если x, z и w истинны, а y ложно, оба условия выполнены. Проверить предложенный набор значений нетрудно: достаточно пройти по условиям. При поиске подходящего набора готовой подсказки уже нет.
У n булевых переменных есть 2ⁿ возможных наборов значений. Полный перебор проверяет их один за другим; добавление одной переменной удваивает число комбинаций. ETH утверждает более тонкую вещь: даже при другом подходе в худшем случае нельзя полностью избавиться от экспоненциальной зависимости.
Согласно ETH, для 3-SAT нет алгоритма со временем 2^(o(n)), с точностью до полиномиальных множителей по размеру входа.
Обозначение o(n) означает, что показатель растёт медленнее n: отношение этих величин стремится к нулю. Поэтому 2^(√n) — пример субэкспоненциальной зависимости, а 2^(0,01n) — всё ещё экспоненциальная. Маленький постоянный коэффициент сам по себе гипотезу не опровергает.
Быстро решить много удачно подобранных формул недостаточно: нужна доказанная оценка для худшего случая. Именно такую гарантию заявляют лаборатории.
Почему вопрос P против NP остаётся открытым
Проблема P против NP проводит другую границу. Класс P включает задачи с ответом «да» или «нет», которые можно решить за полиномиальное время. В классе NP для положительного ответа существует свидетельство, которое можно проверить за полиномиальное время.
Для 3-SAT таким свидетельством служит подходящий набор значений переменных. Если его предоставить, проверить формулу можно быстро. Вопрос в том, существует ли столь же эффективный общий способ определить, есть ли решение. «Быстро» здесь означает полиномиальную зависимость от длины входных данных, например квадрат или куб этой длины.
Разницу между оценками удобно увидеть на трёх выражениях:
Зависимость |
Тип роста |
Что происходит при увеличении n |
n³ |
Полиномиальный |
Размер входа возводится в фиксированную степень |
2^(√n) |
Субэкспоненциальный, но сверхполиномиальный |
Растёт быстрее любой фиксированной степени n |
2ⁿ |
Экспоненциальный |
Каждая дополнительная единица n удваивает значение |
Таблица иллюстрирует типы роста функций. Она не описывает измеренную скорость новых алгоритмов.
3-SAT — NP-полная задача: полиномиальный алгоритм для неё дал бы полиномиальные алгоритмы для всех задач NP.
ETH — более сильное предположение, чем P ≠ NP. Её истинность влечёт P ≠ NP, но опровержение ETH само по себе не устанавливает P = NP. У 3-SAT может существовать субэкспоненциальный алгоритм, который всё равно работает дольше любого полинома.
Что подтверждает проверка в Lean
Lean проверяет, что утверждение следует из заданных определений и аксиом. Человеку остаётся убедиться, что формализованная теорема соответствует исходной задаче. Безошибочное доказательство более слабого утверждения не подтверждает более сильное.
В описании формализации OpenAI уже видна существенная деталь. Рукопись заявляет время:
2^(O(n · log log n / √log n)).
В документе о границах проверки Lean указана более слабая оценка:
2^(O(n · (log log n)² / √log n)).
Оценки приведены для фиксированного k — максимальной длины условия; полиномиальные множители по размеру входа опущены. Дополнительный множитель log log n ухудшает верхнюю оценку времени. При этом обе зависимости остаются субэкспоненциальными и, если доказаны для нужной задачи, достаточны для опровержения ETH. GitHub
Anthropic отдельно отмечает этот предел в README проекта: машина проверяет доказательства, но соответствие формальных утверждений тексту статьи требует человеческого прочтения. Для этого компания вынесла основные формулировки в отдельный короткий файл MainResults.lean.
Что изменится для алгоритмов и криптографии
ETH использовали как исходное предположение для условных нижних оценок. Логика таких работ выглядит примерно так: «Если ETH верна, задача X не может решаться быстрее определённой границы».
Опровержение предположения не делает условную теорему ошибочной, но лишает её основания для вывода о реальном пределе скорости. Сведения задач друг к другу, методы и промежуточные результаты сохраняют ценность.
Здесь есть ещё одна тонкость. Из нового алгоритма для 3-SAT нельзя автоматически получить одинаковое ускорение для любой NP-полной задачи. При сведении одной задачи к другой размер входа может вырасти. Поэтому последствия нужно рассчитывать для каждого конкретного сведения, учитывая, по какому параметру измеряется сложность.
Для разработчиков ПО важен следующий вопрос: при каких размерах данных новый алгоритм начинает выигрывать? Асимптотика описывает рост затрат при увеличении входа. Она скрывает постоянные коэффициенты и не сообщает, будет ли реализация полезна на доступном оборудовании. Anthropic прямо характеризует свой результат как асимптотический, без утверждений о практической скорости решения формул.
По той же причине заявление об ETH не даёт оснований объявлять существующее шифрование взломанным. Для такого вывода нужен конкретный способ атаки, оценка его затрат и применимость к используемым параметрам криптосистемы. Общего утверждения об ускорении 3-SAT для этого недостаточно.
Уильямс рассказал, что спросил OpenAI о возможных последствиях для криптографии. По его словам, компания проверила этот вопрос и не обнаружила оснований считать, что результат приводит к взлому криптосистем. Это пересказ ответа лаборатории в TechCrunch, а не независимый аудит безопасности.
Как учёные собираются проверять результат
Ранее Уильямс сравнил массовую публикацию ИИ-доказательств с DDoS-атакой на математиков: их проверка требует времени специалистов, которого новые тексты не прибавляют.
Теперь OpenAI согласилась открыть материалы по ETH и профинансировать конференцию для обсуждения последствий. Участники внешней группы работают без вознаграждения от компании и без обязательств о неразглашении. Они могут публиковать собственные выводы, включая критику.
Внешняя группа предлагает совместно разбирать доказательство, публиковать объяснения и изучать последствия для других задач. Отдельный вопрос — как признавать вклад тех, кто проверяет и упрощает результат, и кому предоставлять ранний доступ к материалам.
Следить за проверкой можно на сайте рабочей группы. В новых публикациях стоит обращать внимание на четыре вещи:
Точную задачу: алгоритм находит решение, проверяет его существование или считает все решения.
Параметры оценки: что обозначают n и размер входа, какие величины считаются фиксированными.
Объём формальной проверки: совпадает ли доказанная теорема с главным утверждением рукописи.
Практические результаты: есть ли реализация и измерения, позволяющие говорить о скорости на реальных данных.
Если опровержение подтвердится, следующим шагом станет поиск более простых и эффективных алгоритмов. Для этого потребуется понять, какие идеи обеспечили ускорение и где ещё их можно применить.
В блоге Спешу АИI мы разбираем новые исследования, возможности нейросетей и события вокруг их разработчиков. Подписывайтесь, чтобы следить за развитием ИИ и понимать, что стоит за громкими заявлениями. А познакомиться с разными ИИ-моделями на собственных задачах можно в SpeShu.AI — нашем сервисе, который объединяет их в одном месте.