Главное в материале

  • OpenAI заявила об опровержении ETH — ключевого предположения о вычислительной сложности; Anthropic вскоре представила собственное опровержение
  • Компьютерные учёные создали рабочую группу и открытое письмо, попросив OpenAI публично опубликовать доказательства и профинансировать конференцию
  • OpenAI, по словам Уильямса, проверила, не подрывает ли алгоритм криптосистемы, и не нашла уязвимостей

Опровержение ETH и реакция Anthropic

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

Что такое ETH и почему это важно

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

Как сообщество организует проверку

На этот раз OpenAI выстроила публикацию результатов по-разному для трёх дисциплин: математикам работу сбросили на GitHub, компьютерные учёные сформировали рабочую группу и попросили опубликовать доказательства публично и профинансировать конференцию, а физики создали группу, которая определит порядок выпуска их результата. Организатором ответа компьютерной науки выступает профессор MIT Райан Уильямс, который ранее критиковал подход OpenAI, назвав октябрьский сброс доказательств «DDOS-атакой на математиков». Тем не менее он согласился сотрудничать: лаборатория попросила его, а также Рассела Импальяццо и Рамамохана Патури из UC San Diego — авторов ETH 1999 года — помочь интерпретировать решение. Первым шагом стало открытое письмо с призывом к учёным дать обратную связь и обсудить нормы участия ИИ в их работе. «Некоторые части доказательства можно назвать рутинными, но есть две-три чужеродные части — именно они заставили меня подумать: это то, над чем всему сообществу нужно работать вместе», — сказал Уильямс TechCrunch.

Последствия: от криптографии до пересмотра научных работ

За прошедшее десятилетие ETH вошла во множество научных работ, которые придётся пересмотреть, если заявления лабораторий подтвердятся, — одна из причин, по которым Уильямс добивался от OpenAI поддержки конференции. До научных вопросов стоят вопросы кибербезопасности: улучшенный алгоритм мог бы означать, что криптосистемы с определёнными размерами ключей следует считать взломанными. Уильямс рассказал, что первым делом спросил научного руководителя OpenAI Дэна Робертса, проверяли ли они влияние на криптосистемы, и, по его словам, те проверили и были достаточно уверены, что уязвимостей это не создаёт. Сам Уильямс при этом осторожен: «Каждый компьютерный учёный, вероятно, должен немного увеличить вес правдоподобия P = NP, но вес у каждого свой. Это ставит под сомнение многие наши интуиции о том, насколько разрешимы трудные NP-задачи. Но, вероятно, это не окончательный ответ — алгоритм OpenAI вряд ли может быть лучшим из возможных».