OpenAI опубликовала решения трёх сложных научных задач, и одна из них затрагивает гипотезу экспоненциального времени (ETH) — важную опору современной теории алгоритмов. Если заявленный результат выдержит проверку, разработчикам придётся по-новому смотреть на границы вычислимого, а специалистам по безопасности — ещё раз перепроверить привычные криптографические допущения.
Речь не о готовом универсальном ускорителе для всех NP-задач и тем более не о доказательстве равенства P и NP. Но, как сообщает TechCrunch, модели OpenAI и затем Anthropic предложили алгоритмы, которые для определённого класса логических задач работают за субэкспоненциальное время — быстрее, чем допускает ETH.
Почему ETH важна за пределами теории
Гипотеза, сформулированная в 1999 году Расселом Импальяццо и Рамамоханом Патури, утверждает: для задач выполнимости булевых формул с тремя литералами в каждом ограничении — классической 3-SAT — не существует алгоритма с субэкспоненциальным временем работы. Упрощённо: при росте числа переменных сложность таких задач растёт настолько быстро, что радикального алгоритмического обхода не должно быть.
ETH не является доказанной теоремой. Это рабочее допущение, на котором за последние десятилетия построено множество нижних оценок сложности: исследователи использовали его, чтобы объяснять, почему для одних задач не стоит ждать слишком быстрых решений. Поэтому опровержение гипотезы экспоненциального времени — если оно подтвердится независимой экспертизой — не отменит компьютерную науку, но заставит пересмотреть большой пласт результатов, где ETH стояла в основании рассуждений.
Связь с известной проблемой P против NP здесь прямая, но не тождественная. Класс NP объединяет задачи, для которых предложенное решение можно быстро проверить; найти это решение обычно существенно труднее. Судоку — удобный бытовой пример: готовую сетку проверить легко, а заполнить её с нуля может быть мучительно долго. В криптографии похожая асимметрия особенно ценна: знать ключ удобно, подбирать его вслепую — дорого.
Отказ от ETH не означает автоматически, что P равно NP. Он лишь делает более правдоподобной мысль, что некоторые задачи, считавшиеся практически безнадёжными, могут иметь более быстрые алгоритмы. Профессор MIT Райан Уильямс, который помогает организовать реакцию научного сообщества, сформулировал это аккуратно: компьютерным учёным стоит чуть серьёзнее относиться к возможности P = NP, но вес этого аргумента каждый оценит по-своему.
Не релиз, а проверка под нагрузкой
Публикация OpenAI вызвала не только интерес, но и раздражение у части исследователей. Ранее Уильямс называл масштабные выгрузки доказательств от лаборатории «DDoS-атакой на математиков»: даже сильному сообществу нужны месяцы, чтобы разобрать нетривиальный текст, найти скрытые предположения и воспроизвести ключевые шаги. В нынешнем случае он согласился участвовать в разборе вместе с Импальяццо и Патури.
По словам Уильямса, часть доказательства выглядит достаточно стандартно, но в нём есть два или три фрагмента, которые он охарактеризовал как «инопланетные». Именно они требуют коллективной проверки. Для компьютерных наук уже создана рабочая группа: она попросила раскрыть доказательства публично, собрать отзывы специалистов и провести конференцию при поддержке OpenAI. Математикам материалы выложили на GitHub, а физики решили отдельно определить формат публикации своего результата.
Реакция конкурентов добавила сюжету остроты. Математик Anthropic Левент Альпёге предположил, что OpenAI могла опираться на уже существующие идеи. Спустя несколько часов Anthropic представила собственное заявление об опровержении ETH. Это не делает ни один из результатов автоматически верным: в теории сложности приоритет, корректность и обобщаемость алгоритма нужно устанавливать по формальному доказательству, а не по скорости пресс-релиза.
Для инженерных команд практический вывод пока скромнее громких заголовков. Не нужно срочно переписывать оптимизаторы, менять криптографию или объявлять NP-задачи решёнными. Но стоит следить за тем, какие именно классы задач и асимптотики подтвердят эксперты. История показывает, что формально «чуть более быстрый» алгоритм иногда годами остаётся академическим любопытством, а иногда меняет подходы к планированию, верификации, компиляторам и поиску.
Вопрос криптографической безопасности исследователи уже поднимали. Уильямс рассказал, что сразу спросил научного руководителя OpenAI Дэна Робертса, затрагивает ли алгоритм реальные криптосистемы. По его словам, лаборатория проверила этот риск и была достаточно уверена, что немедленных компрометаций результат не даёт. Формулировка намеренно осторожная: конкретные схемы, параметры и пределы применимости алгоритма ещё должны пройти внешнюю проверку.
Главный эффект этой истории может оказаться не в мгновенном взломе сложных задач, а в изменении научного процесса. ИИ-лаборатории уже способны генерировать результаты, которые экспертам приходится разбирать всем полем, а не силами одной группы. Подтвердится ли гипотеза экспоненциального времени как опровергнутая или в доказательствах найдётся ограничение, станет ясно после публичного разбора — материалы и контекст публикации доступны у .
