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