OpenAI опубликовала 67-страничную статью, в которой утверждается, что ИИ компании опроверг гипотезу экспоненциального времени (ETH). Эта гипотеза восходит к 1999 году и не имеет никакого отношения к ethereum, цене ethereum или сооснователю Vitalik Buterin. Это утверждение вызвало обсуждение среди математиков и пользователей криптовалют на X. Пользователь X Takumi пошутил: «Черт, алго-трейдеры только что уничтожили $ETH». Эндрю Цзян написал: «Виталик с тех пор очень тихо себя ведет».
Компьютерные ученые Рассел Импаглиаццо, Рамамохан Патури и Фрэнсис Зейн предложили ETH. Гипотеза утверждает, что решение логической задачи 3-SAT не может быть намного быстрее, чем перебор всех возможных комбинаций. Задача 3-SAT заключается в поиске присваиваний истинности или ложности, удовлетворяющих правилам, включающим по три варианта одновременно. OpenAI отмечает, что сотни научных статей опираются на ETH для установления вычислительных ограничений в теории графов, вычислительной биологии, базах данных и геометрии. OpenAI утверждает, что опровержение ETH возрождает вопросы о возможном ускорении и может направить исследования в сторону разработки более эффективных алгоритмов.
Документ имеет дату 17 октября и дату редактирования 25 октября. В нем представлен детерминированный алгоритм, не использующий случайность, для подсчета всех удовлетворяющих назначений за субэкспоненциальное время. Субэкспоненциальное время означает, что требуемая работа растет медленнее, чем любая экспоненциальная функция от числа переменных. Подсчет удовлетворяющих назначений сложнее, чем определение наличия хотя бы одного удовлетворяющего назначения, поэтому данный алгоритм подсчета также решает задачу принятия решений. OpenAI сообщает, что ИИ обнаружил заявленное опровержение 16 октября. OpenAI утверждает, что результат был формализован 17 октября с использованием Lean — программного обеспечения, которое механически проверяет каждый логический шаг. Документ и формализация доступны на GitHub. Ранее в этом месяце OpenAI опубликовала через GitHub 722 математических рукописи, но только 162 из них содержали компьютерно проверенный основной результат.
Импальяццо, Патури и Райан Уильямс из MIT возглавляют независимое расследование этого утверждения. Три исследователя предупредили в открытом письме, что участие не следует интерпретировать как сертификацию. Исследователи заявили, что вывод такой важности требует строгого независимого обзора и объяснения, которое другие исследователи смогут воспроизвести, оспорить и развить. OpenAI сообщает, что участники не получают вознаграждения и не подписывали никаких соглашений о неразглашении. OpenAI согласилась опубликовать все исходные данные и профинансировать конференцию по результатам.
OpenAI предупреждает, что выявление полезных алгоритмов и перевод теоретических достижений в практические результаты потребуют значительных дополнительных исследований. В статье не доказывается, что все задачи класса NP допускают решения за субэкспоненциальное время. Класс P включает задачи, которые компьютеры могут решать эффективно, а класс NP — задачи, решения которых можно проверить эффективно. Проблема P против NP, заключающаяся в вопросе, всегда ли эффективная проверка подразумевает эффективное решение, остается нерешенной.
Anthropic затем опубликовала статью, приписываемую Claude, под названием «A 2^o(n) Time Algorithm for 3-SAT» и датированную 26 октября. В сопутствующем репозитории указано, что алгоритм был обнаружен внутренней исследовательской версией Claude, который также решает ETH. В репозитории предупреждается, что результат касается асимптотического поведения и не делает никаких утверждений о практическом решении формул. В сентябре Claude формализовал Великую теорему Ферма с помощью Lean. Математик Теренс Тао предупредил в сентябре, что даже слухи о исследованиях по проблеме могут спровоцировать масштабные усилия с использованием ИИ до того, как оригинальный проект полностью сформируется.
OpenAI недавно внесла 5 миллионов долларов в Фонд Симонса. Эти средства будут использованы для поддержки семинаров, конференций и специальных программ, помогающих исследователям анализировать и расширять результаты, полученные с помощью ИИ.