Лаборатории передового ИИ заявили, что их модели опровергли гипотезу экспоненциального времени. Что это значит?

На публикации лаборатории исследователи отреагировали и с воодушевлением, и с тревогой. Математик Anthropic Левент Алпёге предположил, что OpenAI опиралась на уже существовавшие работы. Несколько часов спустя Anthropic опубликовала собственное опровержение гипотезы.

На этот раз OpenAI по-разному организовала публикацию результатов в трёх дисциплинах. Математики получили работу на GitHub. Специалисты по компьютерным наукам создали рабочую группу, попросили открыть доказательства и профинансировать конференцию для их обсуждения. Физики также сформировали рабочую группу — она решит, как опубликовать их результат.

Профессор MIT Райан Уильямс организует реакцию специалистов по компьютерным наукам на новое открытие. Его исследования посвящены вычислительной сложности. Ранее в октябре он критиковал OpenAI за публикацию большого объёма доказательств, назвав её «DDoS-атакой на математиков».

Тем не менее Уильямс согласился сотрудничать с передовыми ИИ-лабораториями, чтобы помочь разобраться в идеях, важных для его области. Об этом он рассказал TechCrunch. OpenAI попросила его вместе с компьютерными учёными из Калифорнийского университета в Сан-Диего Расселом Импальяццо и Рамамоханом Патури проанализировать решение. Импальяццо и Патури впервые опубликовали экспоненциальную временную гипотезу в 1999 году.

Сначала учёные выпустили открытое письмо: они попросили откликнуться исследователей, занимающихся этими задачами, и обсудить нормы использования вклада ИИ в научную работу.

По словам Уильямса, некоторые части доказательства OpenAI выглядят рутинными, но в нём есть два или три непривычных элемента. Именно они убедили его, что обсуждать работу нужно всей научной области.

Что такое P и NP

Экспоненциальная временная гипотеза относится к более широкому кругу вопросов, известных как проблема P против NP. Она десятилетиями занимает специалистов по компьютерным наукам и учёных из других областей. В упрощённом виде вопрос таков: можно ли быстро решать любую задачу, для которой ответ можно быстро проверить?

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

Учёные пока не доказали, что это верно всегда. Уильямс объясняет, что равенство P = NP означало бы: можно не только быстро проверить готовое решение судоку, но и быстро найти его. И так — для любой задачи, ответ на которую можно быстро проверить. По его словам, это кажется слишком хорошим, чтобы быть правдой.

Поэтому большинство учёных предполагают, что P ≠ NP. Экспоненциальная временная гипотеза служила аргументом в пользу этой идеи: для определённого класса сложных логических задач даже самому быстрому алгоритму нужно экспоненциально больше времени, когда растёт число переменных.

OpenAI и Anthropic утверждают, что их модели нашли алгоритмы, решающие такие задачи за субэкспоненциальное время — быстрее, чем считалось возможным. Если результаты подтвердятся, это может опровергнуть экспоненциальную временную гипотезу и открыть путь к алгоритмам, в целом подтверждающим P = NP.

По мнению Уильямса, специалистам по компьютерным наукам стоит немного серьёзнее отнестись к правдоподобию P = NP, хотя степень уверенности у каждого может быть разной. Новые результаты ставят под вопрос привычные представления о том, насколько разрешимы сложные задачи NP. При этом Уильямс не считает ответ окончательным: он сомневается, что алгоритм OpenAI — лучший из возможных.

Что предстоит проверить

Экспоненциальную временную гипотезу десятилетиями включали в научные статьи. Если утверждения ИИ-лабораторий выдержат проверку, многие из этих работ придётся пересмотреть, говорит Уильямс.

Он добивался от OpenAI поддержки конференции, потому что результаты могут повлиять на исследования многих учёных. Теперь нужно разобраться не только в самих алгоритмах, но и в том, как в свете новых данных должны измениться основы области.

До обсуждения научных последствий возникают вопросы кибербезопасности. Уильямс отметил, что более эффективный алгоритм может означать уязвимость криптографических систем, использующих ключи определённой длины. Один из первых вопросов, которые он задал руководителю научного направления OpenAI Дэну Робертсу, — проверили ли в компании влияние результата на криптографию и не стали ли какие-либо системы небезопасными. По словам Уильямса, OpenAI провела такую проверку и была достаточно уверена, что новые алгоритмы не означают взлома криптографических систем.

Новый подход к научным открытиям с помощью ИИ пока развивается. Несмотря на реальные опасения, особенно связанные с подготовкой следующего поколения учёных, Уильямс настроен оптимистично. По его мнению, ему как специалисту по компьютерным наукам, работающему с высшей математикой, возможно, было проще привыкнуть к переменам, чем чистым математикам.

Уильямс добавил, что ИИ побуждает учёных ставить перед собой более амбициозные задачи и задумываться, какие вопросы исследовать дальше, если прежние проблемы стали для ИИ лёгкой добычей.