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

Они независимо пришли к результату

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

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

Исследование проводили в Италии