Соавтор гипотезы экспоненциального времени назвал её опровержение ИИ «ошеломляющей новостью»История·Модели OpenAI решают открытые задачи математики
ИИ помог опровергнуть гипотезу, на которой строились оценки сложности множества задач. Формальная проверка уже есть, но практическое ускорение начинается на задачах недостижимого размера, а вывод ещё разбирают специалисты.
Источники 2
Рассел Импальяццо, в 1998 году предложивший гипотезу экспоненциального времени (ETH) вместе с Рамамоханом Патури, назвал её опровержение «очень ошеломляющей новостью». ETH утверждала, что задачу выполнимости булевых формул 3-SAT нельзя решить за субэкспоненциальное время; от неё зависят условные оценки сложности в сотнях работ. По описанию OpenAI, опубликованные 26 октября работы OpenAI и Anthropic независимо предлагают алгоритмы со временем 2^o(n); созданные с существенным участием ИИ доказательства проверены в системе Lean. Импальяццо отметил, что исследователи скорее ожидали падения более строгих версий гипотезы. Практический эффект пока ограничен: по оценкам, приведённым The New York Times, проверенная граница OpenAI улучшает перебор лишь примерно от 10^2389 переменных, а вариант Anthropic для формул с пятью условиями на переменную — от 10^10000. Результат не отвечает на вопрос о равенстве P и NP и не ускоряет NP-задачи в целом. Импальяццо, Патури и Райан Уильямс участвуют в независимом разборе работы, но подчёркивают, что это не означает сертификации результата.