Компания OpenAI обнародовала решения трёх крупных математических задач, которые долгое время ставили исследователей в тупик. Одно из них стало неожиданным опровержением гипотезы об экспоненциальном времени (ETH, Exponential Time Hypothesis) — устойчивого допущения в информатике, во многом определяющего представления о вычислительной сложности. Как и после предыдущих публикаций доказательств от этой лаборатории, научное сообщество отреагировало смешанными чувствами — воодушевлением и тревогой, сообщает TechCrunch.
Математик из Anthropic Левент Альпёге высказал предположение, что OpenAI опиралась на уже существующие работы, а спустя несколько часов Anthropic опубликовала собственное опровержение ETH. При этом сам процесс у OpenAI меняется: на этот раз для каждой из трёх дисциплин выбрали отдельный формат. Математики получили работу на GitHub, специалисты по информатике сформировали рабочую группу и попросили открыть доказательства для публики, а также профинансировать конференцию для их обсуждения, а физики создали группу, которая определит порядок публикации их результата.
Профессор Массачусетского технологического института Райан Уильямс, занимающийся вопросами вычислительной сложности, организует ответную реакцию своего научного направления. Ранее он критиковал подход OpenAI и называл октябрьскую публикацию доказательств «DDOS-атакой на математиков». Тем не менее он согласился сотрудничать с лабораторией, чтобы помочь продвинуть важные для отрасли идеи, и рассказал об этом TechCrunch. OpenAI попросила его помочь с трактовкой решения вместе с учёными из Калифорнийского университета в Сан-Диего Расселом Импальяццо и Рамамоханом Патури, которые впервые опубликовали ETH в 1999 году.
Первым шагом стало открытое письмо с призывом к учёным, интересующимся этими задачами, прислать отзывы и обсудить нормы вклада искусственного интеллекта в их работу. «Некоторые части [доказательства OpenAI], возможно, можно назвать рутинными, но есть две-три части, выглядящие чужеродно, и именно они заставили меня подумать: вот это то, над чем всему сообществу нужно работать вместе», — заявил Уильямс TechCrunch. ETH относится к более широкому классу задач P vs NP, которые десятилетиями занимают информатику и смежные области. Упрощённо исследователи пытаются понять, можно ли любую задачу, решение которой легко проверить (NP), так же легко решить (P).
Наглядный пример — судоку: готовое решение можно быстро проверить, но поиск ответа требует времени. Эта закономерность лежит в основе криптографических систем: при наличии ключа зашифрованное сообщение раскрывается, а взлом эффективного шифра занимает слишком много времени, чтобы быть полезным. При этом учёные пока не доказали, что так бывает всегда. «P = NP означает, что вы не только можете проверить решения судоку, когда они есть, но и просто их породить», — пояснил Уильямс. По его словам, это утверждение кажется слишком хорошим, чтобы быть правдой, поэтому большинство учёных исходят из того, что P ≠ NP, а ETH служила тому подтверждением: даже самому быстрому алгоритму требуется экспоненциально больше времени по мере роста числа переменных в особом классе логических головоломок.
OpenAI и Anthropic заявляют, что их модели нашли алгоритмы, решающие такие головоломки за «субэкспоненциальное» время, то есть быстрее, чем считалось возможным. Если это так, ETH может быть опровергнута, а перед алгоритмами, в целом работающими при P = NP, открывается путь. «Каждому специалисту по информатике, вероятно, стоит придавать чуть больше веса правдоподобности P = NP, хотя у каждого этот вес может быть разным», — отметил Уильямс. По его мнению, это ставит под вопрос многие прежние интуиции о разрешимости сложных NP-задач, но вряд ли является окончательным ответом: алгоритм OpenAI вряд ли может быть лучшим из возможных. Устойчивость ETH привела к тому, что её включали во множество научных работ последнего десятилетия, и их придётся пересмотреть, если заявления лабораторий подтвердятся. Отдельно Уильямс поднял вопрос кибербезопасности: улучшенный алгоритм мог бы означать взлом криптосистем с определёнными размерами ключей, поэтому он спросил научного руководителя OpenAI Дэна Робертса, проверяли ли они влияние на криптосистемы и не стало ли что-то уязвимым; по его словам, проверка показала, что взломов это не подразумевает.