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