Матокалипс

Ночь, когда роботы взялись за неприступное

… потом они пришли за Навье—Стоксом, и я ничего не сказал, потому что никогда не работал над Навье—Стоксом. Но когда они пришли за RL vs. L, я понял, что дело серьёзно

— друг блога Омер Рейнгольд

Вчерашний вечер девятилетний сын тянул за язык жену Скотта Ааронсона — теоретика сложности Дану Мошковиц: «Мам, я слышал, тебя размазало! Робот решил математическую задачу, над которой ты работала всю карьеру! О-о-о!»

Хотя сын вёл себя как балда, он был прав. Хочешь ты этого или нет, вчера был, безусловно, один из величайших дней в истории математики. Среди 372 огромных результатов, выпущенных вчера OpenAI на рекомендацию консультативной группы Тимоти Гауэрса, Эдварда Виттена и других выдающихся математиков, оказалось доказательство гипотезы об уникальных играх (UGC) Субхаша Хота — задачи, над доказательством которой Дана работала с тех пор, как я её знаю. (Гипотеза об уникальных играх подразумевает, что целый спектр задач оптимизации действительно NP-трудны, даже если хочется лишь приближение немного лучше, чем даёт релаксация полуопределённого программирования — один из основных инструментов в арсенале этих учёных.)

Или, по крайней мере, мы довольно уверены, что это доказательство! Есть сертификат Lean — как и для некоторых из остальных 372 прорывных результатов (но не для всех). Однако похоже, что ни один человек пока не разобрался с какой-то из этих доказательств; гонка к пониманию только началась. Чтобы почувствовать, как эта гонка будет выглядеть, вот что писала мне Дана вчера ночью:

Это похоже на текст человека под психоделиками. Так много непонятного и не имеет смысла. Много ссылок на предыдущие работы без объяснения, почему их можно использовать несмотря на результаты невозможности.

По сути, статья написана так ужасно, что её невозможно читать без помощи AI.

Я попросила Astra дать разумные утверждения о полноте и корректности шумного гаджета, и она их дала, комбинируя утверждения со всей статьи.

У них также есть прямые оптимальные доказательства NP-трудности приближения для основных применений UGC (Max Cut и все CSP), которые обходят саму UGC.

Доказательство UGC придумывает совершенно новый причудливый код с шумовым тестом. Это какая-то сумасшедшая рекурсивная конструкция.

Это не длинный код, не короткий код — какая-то чужеземная бредятина.

Я всё ещё думаю, что может быть доказательство, которое использует код половинок пространства (что естественнее).

Цитирования часто нерелевантны и запутанны.

Возможное будущее — это мир математики, который будет прекрасен, если у тебя есть зрение и творческие идеи, которые AI может проверить и реализовать.

И, конечно, нам есть чему учиться у инопланетян.

Если интересно, какие эмоции испытывает Дана — наверно, все сразу! Хотя центральное стремление всей её карьеры рухнуло перед роботом, для неё есть как минимум два смягчающих фактора. Во-первых, она может чувствовать себя оправданной: гипотеза об уникальных играх оказалась верна, в чём она никогда не сомневалась, хотя многие её коллеги сомневались. Во-вторых, все мы в математике, теоретической информатике и математической физике — по крайней мере те, кто заботился о решении чётко сформулированных проблем — теперь в одной лодке.

Сокровища из пещеры Аладдина

Кроме гипотезы об уникальных играх, вот небольшая выборка из того, что захватит внимание в ближайшие недели:

• L=BPL (то есть вероятностный логарифмический размер памяти и детерминированный логарифмический размер памяти — одно и то же), одна из больших гипотез о дерандомизации, не считая P=BPP. Хотя её истинность никогда не вызывала серьёзных сомнений, целое подсообщество было сосредоточено на её доказательстве.
• Быстрое преобразование Фурье и целочисленное умножение за время меньше, чем O(n log n), преодолевая барьер, стоявший с 1960-х годов. Новое время работы, если интересно, O(n log^{0.9999999999999} n), плюс-минус пара девяток.
• Положительное решение задачи синтеза унитарных преобразований, которую Грег Купербе́рг и Скотт поставили ещё в 2007 году. Для каждого n-кубитного унитарного преобразования U существует классический оракул A, такой что U можно реализовать за квантовое полиномиальное время с доступом к A. Это противоположно тому, чего ожидали большинство. Следствия могут быть важны, например, для задачи декодирования излучения Хокинга из чёрной дыры и многих других проблем в квантовой теории сложности — если бы у нас был эффективный способ конструировать оракул A, чего эта статья не даёт.
• Чётность не в QAC⁰ — одна из больших задач квантовой теории сложности с 1999 года, над которой закрывались многие коллеги.
• Почти 4-й степени разделение между случайной и квантовой сложностью запросов для полных булевых функций. Любимая задача с 1998 года (!), когда было известно лишь, что оптимальный разделяющий показатель находится между 2 и 6. За последние несколько лет мы знали, что он между 3 и 4. Наконец эта история закрыта.
• Суперквадратичное разделение между чувствительностью и блочной чувствительностью.
• Закон площади для двумерных гапфулов Гамильтонианов. Одна из главных открытых проблем в сложности Гамильтонианов.
• Матричное умножение за O(n^9/4) — рациональный показатель наконец (!) и совершенно другой подход, чем для O(n^2.373) и так далее.
• Ω(n³) нижняя граница для детерминантной сложности перманента, улучшающая предыдущую квадратичную границу.
• Случайный полиномиальный алгоритм приближённого подсчёта числа совершенных паросочетаний в общем графе, а также случайный почти линейный алгоритм для поиска максимального паросочетания в таком графе.
• Неразрешимость решения полиномиальных уравнений над рациональными числами — вероятно, самая большая открытая проблема в теории вычислимости (учти, что неразрешимость решения диофантовых уравнений, то есть полиномиальных уравнений над целыми числами, была доказана в 1970-х, дав отрицательный ответ на 10-ю проблему Гильберта).

Любой из вышеперечисленных результатов в одиночку мог бы быть «результатом года» в какой-то области (а в некоторых случаях, как «Уникальные игры» и L=BPL, по всей информатике). Есть ещё много чего, что я пропустил — если что-то заставило твои глаза вылезть из орбит, поделись в комментариях! Есть одинаково поразительные чудеса в теории чисел, комбинаторике, алгебраической геометрии, анализе и почти в каждой области математики, большинство из которых я никогда не пойму, хотя стоит отметить, что там есть частичный прогресс к гипотезе Римана и гипотеза Ходжа и гипотеза Бёрча—Суиннертона—Дайера (то есть большинство оставшихся задач тысячелетия).

Можно утешиться тем, что отсутствует из списка. P≠NP там нет, и даже P=BPP или NEXP⊄P/poly не было, и уж точно не из-за отсутствия попыток. Похоже, величайшие открытые проблемы теоретической информатики действительно очень сложны!

Две модели, две стратегии

О, чуть не забыл: за один день до слива OpenAI, то есть в понедельник вечером, Вирджиния Уильямс и Джош Альман выложили препринт на arXiv, решивший задачу 3SUM за O(n^1.9992), и задачу кратчайших путей между всеми парами за O(n^2.9995), опровергнув полувековые гипотезы о том, что правильные ответы были n^2-o(1) и n^3-o(1). В этом случае не модель OpenAI подала решающую идею — это была модель Anthropic! Но Anthropic выбрала другой подход, чем OpenAI: вместо выкладывания необработанных решений миру, она дала Вирджинии и Джошу возможность написать и объявить обработанную версию в обмен на компенсацию.

Эти два подхода стали основными моделями для коммуникации прорывов в AI математике, и у обоих есть сильные и слабые стороны. «Модель OpenAI» запускает сумасшедшую гонку между людьми за разбором и объяснением неряшливого AI доказательства (работу, которая легко может оказаться благодарной за спасением, едва кредитуемой, конкурентной и не очень весёлой), в то время как «модель Anthropic» ставит приватную компанию в позицию выбирать и выбирать, какие математики человеческие будут послами AI. Не знаю, что вы думаете?

Немного цифр и фактов

Для тех, кому интересно: похоже, модель AI, которая произвела все эти чудеса, была не специально изготовленной конструкцией из 10 000 агентов, сжигающей миллионы долларов вычислительной мощности, как использовалась, например, для построения конечного времени взрыва для уравнений Навье—Стокса. Вместо этого это была просто последняя внутренняя модель OpenAI — та, которая может быть выпущена платным клиентам ChatGPT в течение следующих пары месяцев, в зависимости от рекомендаций совета по безопасности OpenAI! (Мой девятилетний сын: «О, они определённо не должны её выпускать. Если она может решить все эти математические задачи, она никак не может быть безопасна.») Похоже, использовали примерно 3 часа вычислений на уровне GPT-Pro в среднем на решённую задачу.

Также, если интересно: похоже, они пробовали модель примерно на 8 000 задачах. Так что прямо сейчас она «всего лишь» решает ~5% долгостоящих открытых математических проблем, которые её спрашивают, проблем, над которыми целые сообщества тратили годы, после одной трёхчасовой попытки.

Сообщество в действии

Был рад видеть, как сообщество теоретической информатики встало на высоту. В Simons Institute в Беркли, здесь в UT Austin и в других местах, слышу истории о том, как исследователи спешат разбираться с рукописями и понимать их и объяснять — потому что что ещё нам делать? Как ещё мы продолжим мастерство, которому посвятили большую часть своей жизни?

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

В журнале Quanta Йордана Цепелевиц попыталась другую метафору:

Это как если бы тебя телепортировали на вершину высокой горы. Вокруг тебя туман, ты не знаешь, где находишься и что вокруг. Ты не знаешь, как твоя гора связана с другими, и у тебя нет оборудования, чтобы исследовать, нет способа помочь кому-то ещё присоединиться к тебе. Если бы ты сам взбирался на гору, ты бы испытал, как человеческое тело адаптируется к высоте и изменениям уровня кислорода. Возможно, тебе пришлось бы придумать инструменты для навигации, для подъёма по крутым скалам или построения убежища. Ты мог бы встретить другого исследователя, заблудиться вместе в скрытой долине и найти растение, которое можно превратить в спасительное лекарство.

Вместо этого ты сидишь на вершине в темноте, а создатель машины телепортации говорит тебе, что она может исследовать дикую природу лучше, чем любой человек.

Для любой из этих гор, если мы достаточно заботимся, я оптимистичен, что сможем сделать то, что всегда делали: разогнать туман и разобраться с тропой, только теперь используя машину телепортации, чтобы помочь нам ориентироваться. Более сложная задача — воспитать сообщество, которое всё ещё заботится о героическом приключении поиска троп вверх по этим горам в мире с машиной. (О, и я думаю, что одно место, где метафора ломается, это то, что мы всё ещё есть друг у друга, как и раньше!)

Скептики и денаисты

Опыт показал, что, даже сейчас, найдутся люди, которые в покровительственном тоне будут объяснять, почему ничего из этого не реально и ничего не считается. Если бы такие люди были способны впечатлиться чем-то, что происходит в эмпирическом мире, могли бы обновить что-то, они уже были бы впечатлены и уже обновились бы несколько лет назад, задолго до того, как всё достигло уровня реального Матокалипса.

Так что они скажут, может быть, предполагаемые решения вообще не решения, а просто «AI помойка». Или может быть ни одна из 372 хорошо известных открытых проблем, которые были решены, вообще не была настоящей математической задачей, все они были просто возвышенными конкурсными головоломками и банальностями. (В конце концов, всё ещё нет гипотезы Римана!) Или может быть вся дисциплина математики возрастом в 4000 лет нуждается в отбрасывании: оказывается, что это всё была просто головоломочная безделица и банальности; всё, что отличается, это то, что теперь банальность стала видна без маски. В любом случае, то, что действительно имеет значение, это то, что истинный внутренний святилище человеческого творчества не было нарушено и вероятно никогда не будет, и также то, что Сэм Альтман и Дарио Амодей — презренные маленькие ботаны.

Если ты всё ещё сторонник той обречённой мировоззрения, всё ещё на тонущем корабле, я настоятельно призываю тебя прочитать вчерашний другой великий вклад в дискурс об AI, кроме матокалипса OpenAI: а именно открытое письмо Скотта Александра Стивену Пинкеру. Я чувствую некоторую ответственность за это, так как человек, который первым познакомил Стивена Пинкера с существованием рационалистского сообщества, и кто также первым познакомил Стивена Пинкера и Скотта Александра друг с другом (они оба были поклонниками писаний друг друга). И теперь Скотт бросает вызов Стиву на буквальный поединок, с пистолетами!

Для чего бы то ни было: Стив — литературный герой всей моей жизни, как и для Скотта, и я также имею привилегию называть Стива своим другом. Но я нашёл пост Скотта одним из самых разрушительных возражений на что бы то ни было, что я когда-либо читал. И я думаю, что вывод Скотта был совершенно правильным: когда речь идёт об опасности AI, главная проблема Стива сейчас — принять и начать использовать более «Пинкеритскую» эпистемологию.

Terminator 2 как путеводитель в будущее

Вчерашний вечер, вместо того чтобы разбираться с сотнями статей OpenAI и/или писать этот пост, я решил провести время со своими детьми. Они хотели киновечер, так что я предложил фильм, который они раньше не видели (и я не видел десятилетиями), и который казался полным здравого смысла и практического руководства для мира, в котором они будут расти: Terminator 2.

Дополнения

Обновление: Как указали несколько человек, криптография — это подобласть, которая кричащим образом отсутствует из списка OpenAI из 376 статей! Но мои источники говорят мне, что компании AI теперь начали, осторожно и дискретно, исследовать, могут ли их последние внутренние модели взломать важные криптографические протоколы и примитивы. Если они могут, то было бы конечно хорошо бежать впереди, прежде чем остальной мир выяснит то же самое.

Ещё одно обновление: Заявление консультативной группы по математике и искусственному интеллекту очень тщательно сформулировано, не одобряя и не осуждая то, что сделала OpenAI, и стоит прочитать:

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

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

Опубликование этой работы — первый шаг. Это издание — начало, не завершение, процесса человеческого понимания и включения работы в математическое знание. В то же время будущее математического исследования не может состоять только из понимания результатов, произведённых лабораториями AI. Математики должны иметь возможность формулировать свои собственные вопросы, развивать свои собственные подходы и исследовать направления, которые не были выбраны как примеры возможностей системы AI. Справедливый доступ к мощным инструментам исследования и адекватные вычислительные ресурсы необходимы для этой свободы.

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