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

Внутренняя модель OpenAI получила доказательство, опровергающее гипотезу экспоненциального времени — одно из ключевых предположений теории вычислительной сложности. Независимо к такому же результату пришла и модель Anthropic. Гипотеза экспоненциального времени предполагает, что по мере увеличения размера входных данных время, необходимое для решения определенного класса задач, в худшем случае растет экспоненциально. В частности, задачу для булевых формул, согласно этой гипотезе, нельзя решить быстрее, чем за экспоненциальное время в зависимости от числа переменных. Обе компании опубликовали опровержения гипотезы, формализованные на языке Lean. Доказательство OpenAI также позволяет предсказать число решений булевых формул за субэкспоненциальное время. Результаты еще предстоит пройти независимую проверку. В частности, сотрудники OpenAI передали результат группе специалистов по теории сложности, в которую вошли авторы исходной формулировки гипотезы Рассел Импальяццо (Russell Impagliazzo) и Рамамохан Патури (Ramamohan Paturi).

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