Загадка теории чисел, над которой человечество билось десятилетиями, — неужели ИИ решил её всего за 8 страниц?
За последние два дня всё математическое сообщество и круги информатики были в огромном шоке.
18 октября слова специалиста по теории чисел Стэнфордского университета Джареда Дукера Лихтмана в X мгновенно подожгли весь интернет —
«Существование такого доказательства настоятельно указывает на P≠NP».
Триггером для этого заявления стал поразительный лист ответов, только что выданный внутренней моделью OpenAI, — доказательство того, что «нуля Ландау — Зигеля не существует».
Эта ключевая проблема аналитической теории чисел, которая застряла на десятилетия, широко признана академическим сообществом как чрезвычайно сложная.
В результате OpenAI не только решила её, но и оригинальное доказательство на самом деле занимало всего 8 страниц!
Последовали ещё более захватывающие события. Ведущие математики быстро подхватили:
Билл Бэнкс из Университета Миссури сначала написал подробный 19-страничный разбор;
Сразу после этого Брайс Керр использовал биквадратичные расширения
и классические результаты Массера, чтобы сжать доказательство до 6 страниц;
Впоследствии профессор Оксфордского университета Бен Грин сократил его ещё раз, непосредственно дав окончательную 5-страничную версию!
От десятилетий безнадёжной неразрешимости до всего 5 страниц. Профессор Абхишек Саха из Лондонского университета королевы Марии поднял душераздирающий вопрос:
Если эту проблему можно доказать всего за 5 страниц, почему математики упускали её десятилетиями?
Найти её — как взойти на небо, проверить её — как выпить воду
Почему 5-страничное доказательство из теории чисел заставило стэнфордского профессора напрямую подумать о святом Граале информатики — P против NP?
Причина проста.
5-страничное доказательство может прочитать и проверить любой эксперт за несколько часов; но ради этих 5 страниц самые светлые умы человечества бились десятилетиями.
«Найти чрезвычайно трудно, проверить чрезвычайно легко». Эти восемь слов и есть сама глубинная интуиция P≠NP!
В разделе комментариев исследователь Anthropic Джошуа Бэтсон проницательно отметил —
Математическое «очевидно» всегда относительно. Факты доказали, что многие нерешённые проблемы (относительно ИИ) все очевидны!
За шуткой скрывается чрезвычайно серьёзный вопрос: когда ИИ выдаёт более 700 математических рукописей за несколько недель, не приближается ли также проблема тысячелетия P против NP?
Три высокие стены, которые запирали человечество пятьдесят лет
Объяснить P против NP одним предложением: все ли проблемы, ответы на которые можно быстро проверить, также являются проблемами, ответы на которые можно быстро вычислить?
P — это множество проблем, которые «можно быстро решить», а NP — это множество проблем, которые «можно быстро проверить».
Судоку, составление расписания занятий и взлом паролей — всё это относится к классу NP: дайте вам ответ, и вы за секунду проверите, верный он или нет; но чтобы найти его с нуля, можно лишь делать нечто близкое к полному перебору.
Если P=NP, современная криптография мгновенно рухнет, глобальные финансы окажутся полностью незащищёнными, но все сложные задачи обретут предельно короткий путь;
Если P≠NP, это означает, что во вселенной существуют задачи, которые принципиально невозможно сократить.
Эта проблема была поставлена в 1971 году, приз — 1 миллион долларов. Подавляющее большинство учёных считают, что P≠NP, но вот уже более пятидесяти лет никто не может это доказать.
В чём же трудность? Потому что человечество не только не сумело найти ключ, но, напротив, доказало, что существующие инструменты для взлома замков обречены на неэффективность.
Вот знаменитые три «барьера»:
1. Барьер релятивизации (1975): классические методы, опирающиеся на симуляцию и диагонализацию, просто не способны её решить;
2. Барьер естественных доказательств (1994): большинство подходов к доказательству нижних оценок сложности схем, если бы они могли доказать P≠NP, попутно сломали бы генераторы псевдослучайных чисел, что привело бы к самопротиворечию;
3. Барьер алгебраизации (2008): усовершенствованные методы в сочетании с алгебраическими приёмами также были доказаны как недостаточно мощные.
В июне этого года теоретик сложности Лэнс Фортноу пессимистично заявил: в настоящее время у человечества нет даже осуществимого маршрута атаки.
Он предложил претендентам сначала доказать гораздо более простую задачу, например «SAT не имеет алгоритма квадратичного времени», а затем добавил добивающий удар: «И там у вас тоже ничего не выйдет».
Вот противник, с которым предстоит столкнуться ИИ.
719 рукописей бомбардируют стены, 9-летний вундеркинд подбирается вплотную
Столкнувшись с медными и железными стенами, ИИ напрямую предпринял насыщенную атаку.
6 октября OpenAI опубликовал на GitHub сразу 722 рукописи (3 были отозваны на следующий день), классифицированные в 372 семейства результатов.
Внутренняя модель попыталась решить около 4000 открытых задач, в среднем затрачивая лишь около 3 часов вычислений ChatGPT Pro на задачу.
Среди них теоретическая информатика составила 40 семейств. Хотя она не решила напрямую P против NP, несколько работ легли точно на главные дороги, ведущие к ней.
В июне этого года теоретик сложности Лэнс Фортноу писал: помимо симуляции, у нас нет способа справиться с общими алгоритмами полиномиального времени; сложность схем, сложность доказательств, алгебраическая геометрия и другие маршруты все застряли далеко ниже полной мощности полиномиального времени. Его вывод состоял в том, что в настоящее время нет даже одного осуществимого маршрута атаки. По совпадению, шесть результатов OpenAI на этот раз водрузили флаг на каждом из них.
Семейство № 112 (нижние оценки сложности схем глубины 3): наиболее многообещающий маршрут к доказательству P против NP — доказать, что некоторая NP-задача требует «схем сверхполиномиального размера». Человечество долго застревало на
о явных нижних оценках для схем глубины 3; на этот раз ИИ напрямую пересёк этот порог.
Семейство № 102 (Гипотеза об уникальных играх, UGC): Доказана эта ключевая гипотеза, предложенная Субашем Кхотом в 2002 году (включая частичную верификацию в Lean). Она тесно соседствует с проблемой P vs NP и значительно усиливает границы неаппроксимируемости многих NP-трудных задач оптимизации.
Фундаментальные алгоритмы и дерандомизация: Достигнута полная дерандомизация рандомизированного логарифмического пространства (L=RL=BPL); показатель степени матричного умножения сжат до
; целочисленное умножение и DFT опустились ниже
времени.
Вокруг семейства № 102, «Гипотезы об уникальных играх», также произошёл пронзительный эпизод.
Дана Мошковиц, жена известного учёного Скотта Ааронсона, посвятила всю свою карьеру этой гипотезе. В ночь публикации их 9-летний сын подбежал, чтобы подшутить над матерью:
«Я слышал, робот решил задачу, которую ты исследуешь всю свою жизнь!»
Журнал Quanta также сообщил, что команда Дора Минцера из MIT, услышав 11 сентября слухи об OpenAI, поспешила опубликовать собственное доказательство связанного варианта до публикации OpenAI, чтобы не быть обойдённой машиной.
Математики-люди уже начали гонку с ИИ.
Крупные фигуры охлаждают пыл: внешний город взят, городские ворота не пробиты
Однако эксперты, лучше всех знающие область, настроены наиболее спокойно.
Лэнс Фортноу опубликовал на следующий день статью, в которой указал: доля решённых ИИ заданных проблем составляет менее 10%, и ни один из этих результатов ни на шаг не приближает нас к решению проблемы P vs NP.
Хотя Скотт Ааронсон назвал 6 октября «одним из важнейших дней в истории математики», он также отметил: в списке не только отсутствует P≠NP, но и отсутствуют «более мелкие» трудные проблемы вроде P=BPP — явно не потому, что никто не пытался.
Он раскрыл в подкасте: OpenAI и Anthropic используют свои самые мощные внутренние модели, чтобы наперегонки приблизиться к взлому P vs NP, но пока ни одна из них не добилась успеха.
Если посмотреть на это спокойно, на пути к прорыву всё ещё остаются четыре крупных серьёзных препятствия:
1. Верификация далека от завершения: лишь около 42% сопровождаются формализованными доказательствами на Lean, а остальные полностью полагаются на ручную работу. Аронсон признаёт, что почти ни один человек по-настоящему не понял ни одного из этих длинных доказательств.
2. Читаемость крайне низкая: Мошковиц отметила, что единственное игровое доказательство, созданное ИИ, было написано «настолько плохо, что понять его без помощи ИИ невозможно».
3. Lean не всемогущ: машины могут гарантировать лишь правильность рассуждений, но не могут гарантировать, что формализованные определения полностью согласуются с исходной задачей, и не могут судить, важен ли результат.
4. Ключевой маршрут остаётся пустым: ИИ прорвался через схемы глубины 3 и алгебраические схемы, тогда как «нижние оценки для общих булевых схем», которые могли бы подразумевать P≠NP, остаются недоказанными.
Высший парадокс: является ли ИИ живым доказательством P≠NP?
Раз городские ворота ещё не взяты, почему всё же говорят, что «ИИ приближается»?
Потому что три сигнала уже несравнимо ясны.
Во-первых, «сложность» трудных задач была переоценена. Пятистраничное доказательство нуля Зигеля показывает, что некоторым тупикам не хватает лишь одного шага, о котором никто не подумал. Сколько гипотез отделяет всего один слой оконной бумаги? Никто не уверен.
Во-вторых, периферийные позиции расцветают повсюду. Уникальные игры, нижние оценки схем, дерандомизация, умножение матриц... эти вехи на окружающих позициях были интенсивно покорены ИИ, и главное направление рано или поздно будет прорвано.
В-третьих, масштаб и скорость не относятся к человеческому порядку величины. 4000 задач, в среднем по 3 часа на каждую. Когда крупные лаборатории нацелят следующее поколение своих самых мощных вычислительных мощностей прямо на P vs NP, количественное накопление с высокой вероятностью вызовет качественный скачок.
Что касается окончательного исхода, в академических кругах даже возникли интересные разногласия в ставках.
Аронсон по-прежнему делает крупную ставку на P≠NP; но некоторые учёные считают, что если ИИ действительно сможет совершить прорыв, ответ скорее будет P=NP — потому что заставить ИИ найти хитроумный алгоритм гораздо легче вообразить, чем использовать существующую математику для доказательства «невозможности».
Однако самое интригующее и юмористическое в этом всём —
Чем мощнее становится ИИ, тем больше он сам выглядит как живое доказательство P≠NP.
Он потребляет огромные вычислительные мощности, чтобы «искать» доказательства, тогда как люди тратят несколько часов, чтобы «верифицировать» результаты.
Если однажды ИИ действительно сожжёт свои вычислительные мощности и докажет P≠NP, это будет самое совершенное самодоказательство этой проблемы тысячелетия.
Эта статья взята из публичного аккаунта WeChat «Xinzhiyuan», автор: ASI Revelation
