OpenAI и Anthropic заявили, что их исследовательские модели нашли способ быстрее решать один из известных классов вычислительных задач. Если результаты выдержат проверку, учёным придётся пересмотреть гипотезу, на которую исследователи опирались много лет. При этом речь не о путешествиях во времени и не об ускорении компьютеров прямо сегодня.
В чём была проблема
Представьте расписание встреч. У каждого участника есть свои ограничения: один не может утром, другой занят после обеда, а третьему нужно встретиться с первым. Для маленькой группы подходящее расписание найти нетрудно. Когда участников и условий становится много, количество возможных сочетаний быстро растёт.
В информатике есть похожая по духу задача: выяснить, можно ли подобрать значения переменных так, чтобы все условия выполнялись одновременно. Один из её вариантов называется 3-SAT. Найденное решение сравнительно легко проверить, но найти его или убедиться, что решения нет, для некоторых наборов условий может быть трудно.
С полным перебором число вариантов удваивается с каждой новой переменной. Однако учёные давно придумали методы лучше полного перебора. Вопрос глубже: существует ли алгоритм, у которого время решения в худшем случае растёт существенно медленнее экспоненты при увеличении размера задачи?
Гипотеза об экспоненциальном времени, или ETH, предполагает, что для 3-SAT такого алгоритма нет. Это не доказанный закон, а влиятельное предположение: на его основе исследователи строили выводы о сложности многих других задач.
Что предложили OpenAI и Anthropic
OpenAI сообщила, что её система нашла опровержение ETH, и открыла текст работы и формализацию доказательства. Вскоре Anthropic опубликовала работу, в которой исследовательская модель Claude тоже предлагает алгоритм, противоречащий гипотезе.
Обе работы описывают алгоритмы с так называемым субэкспоненциальным временем. Проще говоря, при достаточно большом росте числа переменных их теоретическая оценка растёт медленнее, чем экспоненциальная граница, предполагаемая ETH. Это не значит, что вычисления становятся простыми или занимают секунды.
У Anthropic есть особенно важная оговорка: результат касается поведения алгоритма на очень больших размерах задачи и сам по себе ничего не обещает о скорости на практике. Алгоритм может быть значимым для теории, но не обязательно окажется полезным на обычных компьютерах.
Значит ли это, что ИИ уже всё доказал?
Компании говорят о доказательствах, проверенных с помощью Lean - программы для формальной проверки математических рассуждений. Она помогает проверить, следуют ли записанные выводы из заданных утверждений и правил.
Но остаётся работа для людей: убедиться, что формальная запись соответствует исходной задаче, понять идеи доказательства и оценить последствия. OpenAI привлекла к этой работе внешних специалистов, включая авторов исходной гипотезы. Anthropic тоже отмечает, что соответствие формальной формулировки тексту статьи нужно проверить человеку.
Если выводы подтвердятся, исследователям придётся заново оценить результаты, которые опирались именно на ETH. Это не делает автоматически неверными все их выводы: для каждой работы нужно выяснять, что именно зависело от гипотезы и можно ли обосновать результат иначе.
А что с паролями и другими сложными задачами?
Опровержение ETH не доказывает, что все сложные задачи можно решать быстро. Оно также не решает знаменитую проблему P против NP - вопрос о том, можно ли для каждой задачи с легко проверяемым ответом так же быстро находить решение.
Не следует пока делать и вывод, что привычное шифрование взломано. По словам OpenAI, поиск практических алгоритмов и применение теоретических результатов потребуют дальнейших исследований.
Для обычного читателя здесь интереснее другое: ИИ всё активнее участвует в фундаментальной науке. Но между громким заявлением и понятным, проверенным открытием остаётся большая работа - разобраться в доказательстве, обсудить его с другими исследователями и проверить, к чему оно действительно ведёт.