OpenAI сообщает, что ИИ-модель опровергла гипотезу экспоненциального времени (ETH), поставив под сомнение предположение, на котором исследователи полагались 27 лет. Модель разработала более быстрый алгоритм для логической задачи 3-SAT. Система OpenAI сгенерировала доказательство на естественном языке 16 октября. Команда перевела доказательство на язык Lean на следующий день, что позволило программному обеспечению проверить каждый логический шаг.
Опубликованный алгоритм выполняется примерно за 2^(n/√log n) шагов для входа, содержащего n переменных. Это время выполнения ниже экспоненциальной нижней границы, предсказанной ETH, но всё ещё слишком медленно для практических применений. OpenAI предупреждает, что для достижения практических ускорений необходимы значительные дополнительные исследования. Рассмотрение проведут Russell Impagliazzo и Ramamohan Paturi из Калифорнийского университета в Сан-Диего при участии Райана Уильямса из MIT. OpenAI не претендует на научное признание открытия, следуя более раннему спору, связанному с уравнениями Навье-Стокса.
Импальяццо и Патури ввели ETH в 1999 году. Гипотеза касается 3-SAT, которая ставит вопрос о возможности присвоения значений истинно-ложно переменным при удовлетворении всех связанных условий. Предложенное решение легко проверить, но каждая дополнительная переменная удваивает количество возможных комбинаций для поиска. ETH утверждает, что ни один алгоритм не может избежать экспоненциального роста в худшем случае. OpenAI отмечает, что сотни статей использовали эту гипотезу для установления вычислительной сложности в теории графов, вычислительной биологии и базах данных. Аббревиатура ETH не имеет отношения к тикеру Ethereum.
Результат не доказывает, что P равно NP. Вопрос P против NP заключается в том, можно ли быстро решать все задачи, решения которых можно быстро проверить. ETH сделал более сильное утверждение, чем P ≠ NP, поэтому опровержение ETH не решает этот более широкий вопрос. Президент и сооснователь OpenAI Грег Брокман подчеркнул это различие через несколько часов после объявления. Алгоритм не угрожает напрямую криптографии, защищающей bitcoin и ethereum. Подписи bitcoin используют криптографию на эллиптических кривых, и алгоритм не решает математическую проблему, лежащую в основе этой системы.
Скотт Ааронсон, профессор информатики в Университете Техаса в Остине, сказал, что студенты принесли ему новости о заявленном опровержении. Ранее математические прорывы также опровергали предположения о вычислительных ограничениях. Анатолий Карачуба опроверг гипотезу Андрея Колмогорова об умножении примерно за неделю в 1960 году. Волькер Штрассен в 1969 году пытался доказать оптимальность стандартного умножения матриц, но вместо этого открыл более быстрый метод. Сейчас машины генерируют доказательства, которые люди затем пытаются понять. В том же выпуске также утверждалось о дополнительных доказательствах, связанных с гармоническим анализом и физикой частиц.
Криптограф Мэттью Грин предупредил, что ИИ может подорвать математику, защищающую кошельки. Бенджамин Кауэн, член Экспертного совета по рыночной аналитике BeInCrypto, утверждал, что достижения в дисциплинах, далеких от финансов, в конечном итоге могут изменить рынки. Развитие ИИ все чаще проверяет предположения о вычислительной сложности, на которых основаны цифровые активы.