OpenAI и Anthropic независимо опубликовали доказательства ложности гипотезы об экспоненциальном времени.
ETH — это 27‑летнее допущение в теоретической информатике, согласно которому некоторые задачи нельзя решить существенно быстрее, чем полным перебором. Теперь ведущие ИИ‑лаборатории утверждают, что это не так.
Если доказательства выдержат проверку, это станет самым значимым результатом, сгенерированным ИИ, в информатике на сегодняшний день. А ещё это вынуждает переосмыслить буквально сотни научных работ, которые опирались на истинность ETH.
В этой статье мы объясним, что на самом деле означает гипотеза об экспоненциальном времени, а также свяжем её с задачей P против NP. Мы также рассмотрим, что именно утверждают две лаборатории, как проверялись доказательства и что меняется (а что нет) для криптографии.
P против NP простыми словами
P против NP — это вопрос о том, любая ли задача, для которой легко проверить ответ, так же легко и решается. Это одна из семи задач тысячелетия, и после этой новости она по‑прежнему остаётся открытой.
Классическая иллюстрация — судоку. Проверить заполненную сетку — дело секунд: просканировать строки, столбцы и блоки на повторы. А вот найти решение с почти пустой сетки может быть значительно сложнее, и разрыв растёт взрывным образом по мере увеличения размера сетки.
- P — класс задач, которые компьютер может решить за полиномиальное время, то есть трудоёмкость растёт как n2, n3 и т. п. по мере роста размера входа n.
- NP — класс задач, для которых компьютер может проверить предложенное решение за полиномиальное время.
Любая задача из P принадлежит и NP. Открытый вопрос — верно ли обратное. Большинство компьютерных учёных считают, что P ≠ NP, то есть некоторые задачи принципиально труднее решать, чем проверять. Современная криптография опирается на это убеждение: шифровать просто, но расшифровать без ключа должно быть трудно.
Что такое гипотеза об экспоненциальном времени?
ETH формулируется более остро: она утверждает, что одна конкретная NP‑задача, 3‑SAT, требует экспоненциального времени независимо от изощрённости алгоритма. Её предложили Рассел Импальядцо и Рамамохан Патури из Калифорнийского университета в Сан‑Диего в конце 1990‑х; Фрэнсис Зейн внёс вклад в фундаментальную часть работы.
Задача 3‑SAT
В 3‑SAT дана формула из n булевых переменных и список клауз. Каждая клауза соединяет три условия через ИЛИ, например «x₁ истинно ИЛИ x₄ ложно ИЛИ x₇ истинно». Задача — найти такие значения переменных, чтобы одновременно удовлетворялись все клаузы.
Полный перебор проверяет все 2ⁿ наборов значений, так что каждая дополнительная переменная удваивает работу. Понятно, что уже около 100 переменных делают задачу безнадёжной.
Что утверждает ETH
ETH гласит, что существует константа c > 1, такая что ни один алгоритм не решает 3‑SAT быстрее, чем за cⁿ. Хитрые алгоритмы могут уменьшать основание ниже 2, но никогда не доводят его до субэкспоненциального. Формально: существует δ > 0, такое что 3‑SAT нельзя решить за время O(2δn).
Десятилетиями прогресс соответствовал этой картине. Исследователи постепенно снижали основание, но оно оставалось существенно больше 1. Поскольку 3‑SAT можно сводить ко многим другим задачам, ETH стала рабочей опорой: с её помощью обосновывали, что задачи вроде клики, вершинного покрытия, независимого множества и др. тоже нельзя решить намного быстрее.
Как соотносится новый результат
| Подход | Время работы для 3‑SAT | Растёт экспоненциально? |
|---|
| Полный перебор | 2ⁿ | Да |
| Лучший известный до окт. 2026 (детерминированный) | около 1,328ⁿ | Да |
| Лучший известный до окт. 2026 (рандомизированный) | около 1,308ⁿ | Да |
| OpenAI и Anthropic (окт. 2026) | 2^O(n log log n / √log n) | Нет: субэкспоненциально |
Новая оценка кратко записывается как 2o(n). Цена за добавленную переменную стремится к 1 при росте n — ровно то, что ETH объявляла невозможным.
Что объявили OpenAI и Anthropic
Обе лаборатории независимо пришли к по существу одинаковой субэкспоненциальной оценке и подкрепили статьи машинно проверенными доказательствами в помощнике доказательств Lean.
| | OpenAI | Anthropic |
|---|
| Статья | «The Exponential Time Hypothesis Is False» (67 стр.) | «A 2o(n) Time Algorithm for 3‑SAT» (49 стр.) |
| Модель | Безымянная внутренняя модель | Внутренняя исследовательская модель Claude, указана соавтором |
| Когда найдена ключевая идея | 16 октября 2026 | 16 октября 2026 |
| Публикация | 26 октября 2026 | 26–27 октября 2026 |
| Проверка | Доказательство в Lean слегка более слабой оценки, всё же опровергающей ETH | Доказательство в Lean 4 на базе Mathlib, перепроверено вторым ядром |
| Дополнительные утверждения | Ускорение не распространяется на весь NP | Также опровергает сильную ETH (SETH); новая нижняя граница для схем |
Anthropic утверждает, что Claude нашла ядро алгоритма без участия человека после генерации около 14 миллионов токенов. Метод опирается на тензорные сети и ранговые аргументы. Исследователи затем помогли с финальным текстом статьи.
Почему обе лаборатории нашли это в один день?
Ни одна лаборатория не объяснила синхронность. В статье Anthropic результаты названы независимыми и одновременными, а изложения идут разными математическими путями к по существу одинаковой оценке.
Контекст делает совпадение менее удивительным, чем кажется. Обе лаборатории направляют свои модели на длинные списки открытых задач, и один лишь OpenAI опубликовал сотни ИИ‑сгенерированных математических рукописей в начале октября. ETH — одна из самых известных целей в этой области, и обе модели обучались на одних и тех же публикациях. Независимое одновременное открытие — давний научный паттерн: вспомните Ньютона и Лейбница в анализе или Дарвина и Уоллеса в естественном отборе.
Насколько надёжны доказательства?
Lean подтверждает, что формальное утверждение логически следует из своих аксиом. Он не может подтвердить, что формальное утверждение совпадает по смыслу с текстом статьи. Anthropic отмечает, что соответствие никто машинно не проверяет, а OpenAI говорит, что их файл Lean доказывает чуть более слабую оценку, чем заявлено в заголовке.
Сейчас те же исследователи, которые сформулировали проблему, Импальядцо и Патури, вместе с Райаном Уильямсом из MIT, организуют воркшопы для оценки того, действительно ли формальные утверждения отражают ETH. В их письме подчёркивается, что участие в рецензировании не означает согласия с результатами. По состоянию на момент написания статьи, публичных указаний на изъян не было.
Уильямс отметил, что части доказательства OpenAI выглядят рутинно, тогда как «две‑три инопланетно выглядящие части» ещё нуждаются в пристальном разборе. Импальядцо, один из авторов ETH, назвал результат глубоко удивительным.
Что меняется, а что нет
На практике сегодня почти ничего не меняется (фух): новые алгоритмы обгоняют полный перебор лишь на входах значительно больше любых, которые компьютер вообще способен удержать.
Более быстрых SAT‑решателей не будет
В статье Anthropic сказано, что их метод обгоняет полный перебор только на астрономически больших входах. Для типичных формул с пятью клауза́ми на переменную точка пересечения — число примерно с 10 000 цифрами. В самом общем случае — число примерно со 100 миллионами цифр.
Авторы также отмечают, что их подход вряд ли поможет на чём‑либо меньше примерно 10 миллионов переменных. SAT‑решатели, используемые в проверке микросхем, расписаниях и планировании, от этого результата быстрее не станут.
Криптография не сломана
Результат не затрагивает P против NP. Никто и не утверждает обратного. OpenAI говорит, что проверила, ломает ли алгоритм реальные криптосистемы, и достаточно уверена, что нет.
Теория будет переписана
Больший эффект — в исследованиях. Результаты о трудности, основанные на ETH или SETH, теперь нуждаются в новой опоре, и некоторые исследователи уже говорят, что годы их работы придётся пересматривать. Но падает не всё. Anthropic отмечает, что результат не опровергает задачу об ортогональных векторах, на которой держится множество тонких результатов по сложности.
Почему это важно для ИИ
Главное здесь не 3‑SAT, а то, кто нашёл ответ: две ИИ‑системы независимо опровергли гипотезу, которой специалисты доверяли целое поколение.
ИИ как исследовательский соавтор
Исследователи теперь описывают новые ИИ‑результаты, появляющиеся раз в неделю‑две и вмешивающиеся в уже идущие проекты. Формальные инструменты вроде Lean становятся центральными: они позволяют доверять длинному машинно написанному доказательству без переписывания каждой строки вручную.
Скрытые короткие пути и самосовершенствование
ETH отражала веру в то, что у некоторых задач поиска нет хитрого короткого пути. Если это неверно, другие очевидно трудные задачи тоже могут скрывать сокращения.
Здесь напрашивается открытие алгоритмов как область, где такие короткие пути могут сильно повлиять на рекурсивное самосовершенствование — идею систем ИИ, помогающих проектировать более лучший ИИ. Применение ИИ для поиска быстрых алгоритмов — один из конкретных путей к этому, хотя данный результат напрямую к этому сегодня не ведёт.
Что это значит для специалистов по данным
Тем, кто работает с данными, особенно важны три урока:
- Теория сложности — не только для академии: Знание, почему задача NP‑трудна, подсказывает, когда стоит думать о эвристиках, аппроксимациях или решателях вместо точного поиска.
- Верификация — это навык: По мере того как ИИ генерирует всё больше кода и аналитики, проверка результата (тестами, доказательствами или воспроизводимыми конвейерами) важна не меньше, чем его получение.
- Асимптотика может вводить в заблуждение: «Более быстрый» алгоритм в теории может оказаться бесполезным при реальных размерах задач.
Итог
Если доказательства пройдут экспертную проверку, гипотеза об экспоненциальном времени пополнит короткий список широко принятых гипотез, оказавшихся ложными (как, например, гипотеза Эйлера о сумме степеней). Но P против NP остаётся открытой, а криптография пока в безопасности.
Дальнейшие вехи, за которыми стоит следить: рецензионные воркшопы под руководством авторов ETH, независимые реимплементации алгоритмов и, возможно, ужесточение оценки.
Чтобы освоить основы, лежащие за такими историями, изучайте наши курсы по структурам данных и алгоритмам, программированию на Python и машинному обучению. В них разобрано мышление в терминах Big‑O, которое делает подобные результаты понятнее.
OpenAI и Anthropic независимо опубликовали доказательства ложности гипотезы об экспоненциальном времени.
ETH — это 27‑летнее допущение в теоретической информатике, согласно которому некоторые задачи нельзя решить существенно быстрее, чем полным перебором. Теперь ведущие ИИ‑лаборатории утверждают, что это не так.
Если доказательства выдержат проверку, это станет самым значимым результатом, сгенерированным ИИ, в информатике на сегодняшний день. А ещё это вынуждает переосмыслить буквально сотни научных работ, которые опирались на истинность ETH.
В этой статье мы объясним, что на самом деле означает гипотеза об экспоненциальном времени, а также свяжем её с задачей P против NP. Мы также рассмотрим, что именно утверждают две лаборатории, как проверялись доказательства и что меняется (а что нет) для криптографии.
P против NP простыми словами
P против NP — это вопрос о том, любая ли задача, для которой легко проверить ответ, так же легко и решается. Это одна из семи задач тысячелетия, и после этой новости она по‑прежнему остаётся открытой.
Классическая иллюстрация — судоку. Проверить заполненную сетку — дело секунд: просканировать строки, столбцы и блоки на повторы. А вот найти решение с почти пустой сетки может быть значительно сложнее, и разрыв растёт взрывным образом по мере увеличения размера сетки.
Любая задача из P принадлежит и NP. Открытый вопрос — верно ли обратное. Большинство компьютерных учёных считают, что P ≠ NP, то есть некоторые задачи принципиально труднее решать, чем проверять. Современная криптография опирается на это убеждение: шифровать просто, но расшифровать без ключа должно быть трудно.
Что такое гипотеза об экспоненциальном времени?
ETH формулируется более остро: она утверждает, что одна конкретная NP‑задача, 3‑SAT, требует экспоненциального времени независимо от изощрённости алгоритма. Её предложили Рассел Импальядцо и Рамамохан Патури из Калифорнийского университета в Сан‑Диего в конце 1990‑х; Фрэнсис Зейн внёс вклад в фундаментальную часть работы.
Задача 3‑SAT
В 3‑SAT дана формула из n булевых переменных и список клауз. Каждая клауза соединяет три условия через ИЛИ, например «x₁ истинно ИЛИ x₄ ложно ИЛИ x₇ истинно». Задача — найти такие значения переменных, чтобы одновременно удовлетворялись все клаузы.
Полный перебор проверяет все 2ⁿ наборов значений, так что каждая дополнительная переменная удваивает работу. Понятно, что уже около 100 переменных делают задачу безнадёжной.
Что утверждает ETH
ETH гласит, что существует константа c > 1, такая что ни один алгоритм не решает 3‑SAT быстрее, чем за cⁿ. Хитрые алгоритмы могут уменьшать основание ниже 2, но никогда не доводят его до субэкспоненциального. Формально: существует δ > 0, такое что 3‑SAT нельзя решить за время O(2δn).
Десятилетиями прогресс соответствовал этой картине. Исследователи постепенно снижали основание, но оно оставалось существенно больше 1. Поскольку 3‑SAT можно сводить ко многим другим задачам, ETH стала рабочей опорой: с её помощью обосновывали, что задачи вроде клики, вершинного покрытия, независимого множества и др. тоже нельзя решить намного быстрее.
Как соотносится новый результат
Новая оценка кратко записывается как 2o(n). Цена за добавленную переменную стремится к 1 при росте n — ровно то, что ETH объявляла невозможным.
Что объявили OpenAI и Anthropic
Обе лаборатории независимо пришли к по существу одинаковой субэкспоненциальной оценке и подкрепили статьи машинно проверенными доказательствами в помощнике доказательств Lean.
Anthropic утверждает, что Claude нашла ядро алгоритма без участия человека после генерации около 14 миллионов токенов. Метод опирается на тензорные сети и ранговые аргументы. Исследователи затем помогли с финальным текстом статьи.
Почему обе лаборатории нашли это в один день?
Ни одна лаборатория не объяснила синхронность. В статье Anthropic результаты названы независимыми и одновременными, а изложения идут разными математическими путями к по существу одинаковой оценке.
Контекст делает совпадение менее удивительным, чем кажется. Обе лаборатории направляют свои модели на длинные списки открытых задач, и один лишь OpenAI опубликовал сотни ИИ‑сгенерированных математических рукописей в начале октября. ETH — одна из самых известных целей в этой области, и обе модели обучались на одних и тех же публикациях. Независимое одновременное открытие — давний научный паттерн: вспомните Ньютона и Лейбница в анализе или Дарвина и Уоллеса в естественном отборе.
Насколько надёжны доказательства?
Lean подтверждает, что формальное утверждение логически следует из своих аксиом. Он не может подтвердить, что формальное утверждение совпадает по смыслу с текстом статьи. Anthropic отмечает, что соответствие никто машинно не проверяет, а OpenAI говорит, что их файл Lean доказывает чуть более слабую оценку, чем заявлено в заголовке.
Сейчас те же исследователи, которые сформулировали проблему, Импальядцо и Патури, вместе с Райаном Уильямсом из MIT, организуют воркшопы для оценки того, действительно ли формальные утверждения отражают ETH. В их письме подчёркивается, что участие в рецензировании не означает согласия с результатами. По состоянию на момент написания статьи, публичных указаний на изъян не было.
Уильямс отметил, что части доказательства OpenAI выглядят рутинно, тогда как «две‑три инопланетно выглядящие части» ещё нуждаются в пристальном разборе. Импальядцо, один из авторов ETH, назвал результат глубоко удивительным.
Что меняется, а что нет
На практике сегодня почти ничего не меняется (фух): новые алгоритмы обгоняют полный перебор лишь на входах значительно больше любых, которые компьютер вообще способен удержать.
Более быстрых SAT‑решателей не будет
В статье Anthropic сказано, что их метод обгоняет полный перебор только на астрономически больших входах. Для типичных формул с пятью клауза́ми на переменную точка пересечения — число примерно с 10 000 цифрами. В самом общем случае — число примерно со 100 миллионами цифр.
Авторы также отмечают, что их подход вряд ли поможет на чём‑либо меньше примерно 10 миллионов переменных. SAT‑решатели, используемые в проверке микросхем, расписаниях и планировании, от этого результата быстрее не станут.
Криптография не сломана
Результат не затрагивает P против NP. Никто и не утверждает обратного. OpenAI говорит, что проверила, ломает ли алгоритм реальные криптосистемы, и достаточно уверена, что нет.
Теория будет переписана
Больший эффект — в исследованиях. Результаты о трудности, основанные на ETH или SETH, теперь нуждаются в новой опоре, и некоторые исследователи уже говорят, что годы их работы придётся пересматривать. Но падает не всё. Anthropic отмечает, что результат не опровергает задачу об ортогональных векторах, на которой держится множество тонких результатов по сложности.
Почему это важно для ИИ
Главное здесь не 3‑SAT, а то, кто нашёл ответ: две ИИ‑системы независимо опровергли гипотезу, которой специалисты доверяли целое поколение.
ИИ как исследовательский соавтор
Исследователи теперь описывают новые ИИ‑результаты, появляющиеся раз в неделю‑две и вмешивающиеся в уже идущие проекты. Формальные инструменты вроде Lean становятся центральными: они позволяют доверять длинному машинно написанному доказательству без переписывания каждой строки вручную.
Скрытые короткие пути и самосовершенствование
ETH отражала веру в то, что у некоторых задач поиска нет хитрого короткого пути. Если это неверно, другие очевидно трудные задачи тоже могут скрывать сокращения.
Здесь напрашивается открытие алгоритмов как область, где такие короткие пути могут сильно повлиять на рекурсивное самосовершенствование — идею систем ИИ, помогающих проектировать более лучший ИИ. Применение ИИ для поиска быстрых алгоритмов — один из конкретных путей к этому, хотя данный результат напрямую к этому сегодня не ведёт.
Что это значит для специалистов по данным
Тем, кто работает с данными, особенно важны три урока:
Итог
Если доказательства пройдут экспертную проверку, гипотеза об экспоненциальном времени пополнит короткий список широко принятых гипотез, оказавшихся ложными (как, например, гипотеза Эйлера о сумме степеней). Но P против NP остаётся открытой, а криптография пока в безопасности.
Дальнейшие вехи, за которыми стоит следить: рецензионные воркшопы под руководством авторов ETH, независимые реимплементации алгоритмов и, возможно, ужесточение оценки.
Чтобы освоить основы, лежащие за такими историями, изучайте наши курсы по структурам данных и алгоритмам, программированию на Python и машинному обучению. В них разобрано мышление в терминах Big‑O, которое делает подобные результаты понятнее.