OpenAI заявила об опровержении ETH — гипотезы о скорости вычислений, а не Ethereum

OpenAI опубликовала 67-страничную работу, в которой утверждает, что её модель нашла способ опровергнуть гипотезу экспоненциального времени (Exponential Time Hypothesis, ETH) — предположение из информатики, сформулированное в 1999 году. К Ethereum, его курсу и сооснователю Виталику Бутерину это отношения не имеет.

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

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

Что именно описано в работе

Работа датирована 17 октября и отредактирована 25 октября. В ней описан детерминированный алгоритм (без элемента случайности), который считает все удовлетворяющие наборы таких задач за субэкспоненциальное время: объём работы растёт медленнее любой экспоненты от числа переменных. Подсчёт решений сложнее, чем проверка существования одного, поэтому более трудная задача автоматически решает и более лёгкую.

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

Кто проверяет результат

Независимую проверку ведут Импальяццо, Патури и Райан Уильямс из MIT. Они осторожны в оценке своей роли. «Наше участие не следует воспринимать как подтверждение заявленного результата, — написали трое в открытом письме. — Результат такой значимости требует тщательной, независимой проверки и понимания, которое позволит другим воспроизвести его, оспорить и опереться на него».

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

Практической отдачи пока нет

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

P — класс задач, которые компьютер решает эффективно, NP — задач, чьё предложенное решение можно эффективно проверить.

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

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

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