ИИ утверждает, что опроверг гипотезу экспоненциального времени
OpenAI и Anthropic заявляют, что их ИИ-сгенерированные доказательства опровергают гипотезу экспоненциального времени, заставив исследователей переоценить десятилетия теоретической информатики.
Исследователи из Линчёпингского университета и других учреждений сталкиваются с возможностью того, что ключевое предположение в теоретической информатике может быть неверным после того, как OpenAI и Anthropic опубликовали ИИ-сгенерированные доказательства, бросающие вызов гипотезе экспоненциального времени (ETH). Гипотеза, согласно которой решение некоторых задач требует времени, растущего экспоненциально от размера входных данных, лежит в основе значительной части работы в области проектирования алгоритмов и сложности.
Питер Йонссон, чья статья должна была быть представлена на IEEE Symposium on Foundations of Computer Science, сказал, что его результаты могут стать устаревшими, если выводы ИИ подтвердятся. Он ожидает, что многие докладчики обнаружат, что «ETH неверна, половина моей статьи не работает», и описал ситуацию как одновременно раздражающую и обучающую.
OpenAI разместил доказательства на GitHub как в естественном языке, так и в формате помощника доказательств Lean, и пригласил оригинальных предложивших ETH и других экспертов помочь в проверке работы. Добровольный проект, координируемый через Google-форму, включает участие профессора Калифорнийского университета в Санта-Барбаре Даниэля Локштанова, который предупредил, что подтверждение может сделать десятки его статей «бесполезными».
«Это просто гигантская бомба, сброшенная в центр поля», — сказал Локштанов.
Торе Хусфельдт из IT-университета Копенгагена, который работает над связанными проблемами, назвал результат «фантастическим» и сравнил его с «тем, как кто-то освещает целое подполе прожекторами», хотя также отметил психологическое напряжение исследователей, сталкивающихся с быстрыми ИИ-провоцированными потрясениями.
«Последние несколько месяцев были действительно тяжёлыми. Это много мрака и уныния… некоторые люди действительно депрессируют и очень грустны», — сказал Хусфельдт.
Объём ИИ-созданных рукописей, включая недавнюю 60-страничную работу по ETH, перегрузил академическое сообщество, и некоторые критики указывают на более ранние публикации, содержащие ошибки и выглядящие поспешными.
Виктор Лагерквист, доцент Линчёпингского университета, сказал, что потенциальное опровержение ETH открывает новые пути для задач, которые он ранее отложил в сторону. Аналогично, Локштанов предостерёг, что хотя находка не представляет непосредственной угрозы текущим криптографическим системам, она может в конечном итоге повлиять на конструкции, опирающиеся на предполагаемую вычислительную сложность.
Исследователи подчёркивают необходимость продолжения сотрудничества людей и ИИ для проверки доказательств и изучения их последствий для вычислений и цифровой инфраструктуры.
«Мне всё равно, написано ли доказательство человеком, ИИ или пришельцем, который передал нам это доказательство. Если оно истинно, то мы просто должны использовать его в будущем», — сказал цитируемый исследователь.