В мире информатики произошло событие, которое может перевернуть представления о вычислительной сложности. Компания OpenAI объявила, что её внутренняя модель искусственного интеллекта обнаружила алгоритм, существование которого противоречит гипотезе экспоненциального времени (ETH). Эта гипотеза, сформулированная в 1999 году, на протяжении десятилетий служила фундаментом для сотен работ в теории графов, вычислительной биологии и базах данных.
Суть ETH заключается в описании скорости решения класса комбинаторных задач, где легко проверить готовый ответ, но крайне сложно найти его. Классический пример — судоку: убедиться в правильности расстановки цифр можно за секунды, но поиск решения при увеличении размера поля с 9×9 до 1000×1000 требует колоссальных вычислительных ресурсов. Согласно гипотезе, время решения таких задач всегда растёт экспоненциально с увеличением числа переменных. Однако алгоритм, найденный ИИ OpenAI, демонстрирует более медленный рост, что ставит под сомнение универсальность ETH.
Доказательство было формализовано на языке Lean и выложено на GitHub, что позволяет любому желающему проверить заявление компании. Научную группу проверяющих возглавят профессор MIT Райан Уильямс и двое авторов гипотезы — Рассел Импальяццо и Рамамохан Патури. Осторожность научного сообщества объяснима: ранее OpenAI уже публиковала 722 статьи о нерешённых математических задачах, три из которых пришлось отозвать из-за ошибок. Филдсовский лауреат Теренс Тао назвал массовые ИИ-доказательства «токсичными отходами» в гонке за бенчмарками.
Если доказательство подтвердится, то выводы о невозможности быстрого решения некоторых задач потеряют основания. Однако сами быстрые алгоритмы из опровержения ETH не вытекают — их поиск остаётся отдельной задачей. Это открытие не только бросает вызов теоретической информатике, но и поднимает вопрос о роли ИИ в математике: должен ли искусственный интеллект заниматься фундаментальной наукой или это прерогатива человека? Ответ на этот вопрос, как и проверка доказательства, ещё впереди.