OpenAI заявляет, что модель искусственного интеллекта нашла способ опровергнуть гипотезу экспоненциального времени (ETH) — предположение из информатики, выдвинутое в 1999 году. Это утверждение не связано с Ethereum, криптовалютой, торгующейся под тикером ETH, и с сооснователем Ethereum Виталиком Бутериным.

Тем не менее анонс вызвал шутки в Crypto Twitter. «Проклятые алготрейдеры только что убили $ETH», — написал пользователь по имени Takumi в X, а Эндрю Цзян (Andrew Jiang) пошутил: «Виталик ведёт себя очень тихо с тех пор, как это вышло».

Обсуждаемая ETH была предложена специалистами по информатике Расселом Импальяццо, Рамамоханом Патури и Фрэнсисом Зейном. Согласно ей, логическая задача, известная как 3-SAT, не может быть решена существенно быстрее, чем перебором всех возможных комбинаций переменных. В 3-SAT цель состоит в том, чтобы определить, могут ли присвоения значений «истина/ложь» удовлетворить набору правил, каждое из которых содержит три переменные.

Сотни научных работ опирались на эту гипотезу, чтобы показать, что определённые задачи из теории графов, вычислительной биологии, баз данных и геометрии не могут быть решены быстро, согласно OpenAI. Компания заявила, что опровержение ETH может заново открыть вопрос о том, насколько быстрее эти задачи могут решаться, и помочь исследователям в поиске улучшенных алгоритмов.

«Опровержение ETH заново открывает вопросы о том, насколько быстрее эти задачи могут стать», — написала OpenAI в своей статье в блоге, «и может помочь направить поиск лучших алгоритмов».

Статья OpenAI на 67 страницах, датированная 17 октября и пересмотренная 25 октября, описывает детерминированный алгоритм — то есть не использующий случайность, — который подсчитывает все удовлетворяющие присвоения для таких задач за субэкспоненциальное время. Это означает, что объём работы растёт медленнее любой экспоненциальной функции от числа переменных. Поскольку подсчёт числа решений сложнее, чем определение существования хотя бы одного решения, результат также решает задачу распознавания.

OpenAI сообщила, что её ИИ обнаружил опровержение 16 октября, а 17 октября результат был формализован в Lean — программном обеспечении, механически проверяющем каждый логический шаг. Статья и формализация доступны на GitHub. OpenAI заявила, что это последовало за публикацией 722 математических рукописей ранее в этом месяце, из которых только 162 содержали проверенный компьютером основной результат. Именно этот машиночитаемый формат позволяет независимым исследователям самим проверять каждый шаг аргументации.

Импальяццо, Патури и профессор MIT Райан Уильямс возглавляют независимую проверку утверждения. В открытом письме они предупредили, что их участие не следует воспринимать как одобрение.

«Наше участие не должно рассматриваться как сертификация этого утверждения», — написали они втроём, добавив, что «результат такой значимости требует тщательной независимой проверки и понимания того, что другие могут воспроизвести его, ставить под сомнение и развивать».

OpenAI сообщила, что участники не подписывали соглашений о неразглашении и работают без оплаты. Компания также согласилась опубликовать все исходные данные и финансировать конференцию, посвящённую результату.

Практические последствия остаются неопределёнными. «Поиск таких алгоритмов и превращение теоретических достижений в практические улучшения потребуют значительных дальнейших исследований», — написала OpenAI. В статье также говорится, что результат не устанавливает, что каждая задача из класса сложности NP может быть решена за субэкспоненциальное время.

Это означает, что проблема P против NP остаётся открытой. P состоит из задач, которые компьютеры могут эффективно решать, а NP — из задач, для которых предложенные решения можно эффективно проверять. Нерешённый вопрос заключается в том, можно ли эффективно решить каждую задачу, ответ на которую можно эффективно проверить.

Anthropic присоединилась к обсуждению 26 октября со статьёй, приписываемой Claude и озаглавленной «A 2^o(n) Time Algorithm for 3-SAT». В репозитории, который также затрагивает проблему ETH, говорится, что внутренняя исследовательская модель Claude обнаружила алгоритм. Там же добавляется, что «результат является чисто асимптотическим и ничего не говорит о решении формул на практике».

Claude формализовала Великую теорему Ферма в Lean в сентябре. Математик Теренс Тао предупреждал о возможности пересечения усилий ИИ, написав в сентябре: «Мы теперь увидели, что даже слух о том, что кто-то работает над задачей, может вызвать огромный объём усилий на основе ИИ, чтобы закрыть её до того, как оригинальный исследовательский проект успеет раскрыть свой полный потенциал».

Недавний взнос OpenAI в размере 5 миллионов долларов в Simons Foundation будет поддерживать семинары, конференции и специальные программы, призванные помочь исследователям изучать и развивать результаты, полученные с помощью ИИ.

Источник: Decrypt