Передовые лаборатории искусственного интеллекта утверждают, что их модели опровергли гипотезу экспоненциального роста во времени. Что это значит?

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

Однако процесс OpenAI развивается. На этот раз лаборатория по-разному структурировала выпуски результатов для каждой из трех участвующих дисциплин: математики разместили свою работу на GitHub; специалисты по информатике сформировали рабочую группу, запросили публичный доступ к доказательствам и финансирование конференции OpenAI для их обсуждения; физики сформировали рабочую группу, которая определит, как будут опубликованы их результаты.

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

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

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

«Некоторые части [доказательства OpenAI], возможно, можно назвать рутинными, но да, есть две или три части, которые выглядят совершенно необычно, и именно эти части заставили меня подумать: вау, над этим нужно работать всему сообществу вместе», — сказал Уильямс.

Вы согласны с вариантом P вместо NP?

Проблема ETH относится к более широкому классу задач, известных как P против NP, которые на протяжении десятилетий вдохновляли информатику и многие другие области. В упрощенном виде исследователи пытаются понять, может ли любая задача, решение которой легко проверить (NP), также быть легко решена (P).

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

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

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

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

«Каждому специалисту по информатике, вероятно, следует уделять больше внимания правдоподобности уравнения P = NP, но это мнение может различаться», — сказал Уильямс. «Я думаю, что это ставит под сомнение многие наши интуитивные представления о том, насколько разрешимы [сложные NP-задачи]. Я также думаю, что это, вероятно, не окончательный ответ. Я не думаю, что алгоритм OpenAI может быть лучшим из возможных алгоритмов».

Предстоящая работа для специалистов в области компьютерных наук

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

«Отчасти поэтому я просил или настаивал на том, чтобы OpenAI поддержала конференцию по этой теме — это повлияет на работы многих исследователей, и нам нужно понять, что будет дальше, помимо понимания алгоритмов. Нам нужно понять, как должны измениться основы по сравнению с тем, что было раньше?» — сказал он.

Прежде чем рассматривать научные вопросы, возникают вопросы кибербезопасности. Уильямс сказал, что улучшенный алгоритм может означать, что криптографические системы, использующие определенные размеры ключей, могут считаться небезопасными. Поэтому один из первых вопросов, который он задал руководителю научной работы OpenAI Дэну Робертсу, был: «Проверили ли они, влияет ли это на какие-либо криптографические системы… есть ли теперь что-нибудь небезопасное? И, по-видимому, они проверили и были достаточно уверены, что это не… подразумевает никаких нарушений».

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

Тем не менее, он говорит, что ИИ «заставляет людей быть немного более амбициозными в отношении той работы, которую они выполняют, и глубже задумываться над вопросом: хорошо, если все, чем я раньше занимался, теперь легкодоступно для ИИ, как я могу поднять планку для тех научных вопросов, которые я хочу задавать?»