🤖 Модели OpenAI и Anthropic одновременно опровергли гипотезу экспоненциального времени

Внутренняя модель OpenAI получила доказательство, опровергающее гипотезу экспоненциального времени — одно из ключевых предположений теории вычислительной сложности. Независимо к такому же результату пришла модель Anthropic. Согласно гипотезе, время решения определённого класса задач в худшем случае растёт экспоненциально с размером входных данных — в частности, задачу 3-SAT нельзя решить быстрее экспоненциального времени от числа переменных. Обе компании опубликовали опровержения на языке Lean, а доказательство OpenAI вдобавок позволяет предсказывать число решений булевых формул за субэкспоненциальное время.

Результаты передали на независимую проверку специалистам по теории сложности, включая авторов исходной гипотезы Импальяццо и Патури. Гипотезу используют для обоснования сложности задач в теории графов, вычислительной биологии и геометрии, и в случае подтверждения многие основанные на ней результаты придётся пересмотреть. Практические последствия пока неясны: быстрый алгоритм в теории не гарантирует эффективности на реальных задачах.