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

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

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

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

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

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

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

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

Вы за 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 Дэну Робертсу, был вопрос о том, «проверили ли они, влияет ли это на какие-либо криптографические системы… не стало ли что-то небезопасным? И, судя по всему, проверили — они были достаточно уверены, что это… не означает взлома каких-либо систем».

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

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