Таємниця теорії чисел, над якою людство застрягло на десятиліття — невже ШІ розв'язав її лише за 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 опублікував одразу 722 рукописи на GitHub (3 було відкликано наступного дня), класифіковані у 372 родини результатів.
Внутрішня модель спробувала близько 4000 відкритих проблем, витрачаючи в середньому лише близько 3 годин обчислень ChatGPT Pro на проблему.
Серед них теоретична інформатика становила 40 родин. Хоча вона не розв'язала безпосередньо P vs NP, кілька статей точно влучили на головні шляхи, що ведуть до нього.
У червні цього року теоретик складності Ленс Фортноу писав: окрім симуляції, ми не маємо способу працювати із загальними алгоритмами поліноміального часу; складність схем, складність доведень, алгебраїчна геометрія та інші шляхи всі застрягли далеко нижче повної потужності поліноміального часу. Його висновок полягав у тому, що наразі немає навіть одного життєздатного шляху атаки. За збігом обставин, шість результатів OpenAI цього разу встановили прапор на кожному з них.
Родина № 112 (нижні межі схем глибини 3): найперспективніший шлях до доведення P vs NP — це довести, що деяка NP-проблема потребує «схем надполіноміального розміру». Людство довго застрягало на
щодо явних нижніх меж для схем глибини 3; цього разу ШІ безпосередньо перетнув цей поріг.
Родина № 102 (Гіпотеза унікальних ігор, UGC): Доведено цю ключову гіпотезу, запропоновану Субашем Кхотом у 2002 році (включно з частковою перевіркою в Lean). Вона тісно межує з P vs NP і значно посилює межі неапроксимовності багатьох NP-складних задач оптимізації.
Фундаментальні алгоритми та дерандомізація: Досягнуто повної дерандомізації рандомізованого логарифмічного простору (L=RL=BPL); показник множення матриць стиснуто до
; множення цілих чисел і DFT опустилися нижче
часу.
Навколо родини № 102, «Гіпотези унікальних ігор», також стався пронизливий епізод.
Дана Мошковіц, дружина відомого науковця Скотта Ааронсона, присвятила цій гіпотезі всю свою кар'єру. У ніч публікації їхній 9-річний син підбіг, щоб поглузувати з матері:
«Я чув, що робот розв'язав задачу, над якою ти досліджуєш усе своє життя!»
Журнал Quanta також повідомив, що команда Дора Мінцера з MIT, почувши чутки про OpenAI 11 вересня, поспішила опублікувати власний доказ спорідненого варіанта до публікації 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?
Якщо міська брама не прорвана, чому все ще кажуть, що «ШІ наближається»?
Тому що три сигнали вже є надзвичайно чіткими.
По-перше, «складність» складних проблем була переоцінена. 5-сторінковий доказ нуля Зігеля показує, що деяким глухим кутам бракує саме того кроку, про який ніхто не подумав. Скільки гіпотез відділяє лише один шар віконного паперу? Ніхто не впевнений.
По-друге, периферійні позиції розквітають повсюдно. Унікальні ігри, нижні межі схем, дерандомізація, множення матриць... ці віхи на навколишніх позиціях були інтенсивно підкорені ШІ, і головний напрямок рано чи пізно буде прорваний.
По-третє, масштаб і швидкість не на людському порядку величини. 4000 проблем, у середньому по 3 години кожна. Коли провідні лабораторії націлять наступне покоління своєї найпотужнішої обчислювальної потужності прямо на P vs NP, кількісне накопичення з високою ймовірністю спричинить якісну зміну.
Щодо остаточного результату, то в академічних колах навіть виникли цікаві розбіжності в ставках.
Аронсон все ще робить велику ставку на P≠NP; але деякі науковці вважають, що якщо ШІ справді зможе зламати проблему, відповідь швидше за все буде P=NP — тому що змусити ШІ знайти хитрий алгоритм набагато легше уявити, ніж використати наявну математику, щоб довести «неможливість».
Однак найцікавіша та найкумедніша частина всієї справи —
Чим потужнішим стає ШІ, тим більше він сам виглядає як живий доказ P≠NP.
Він споживає величезну обчислювальну потужність, щоб «шукати» докази, тоді як люди витрачають кілька годин, щоб «перевірити» результати.
Якщо одного дня ШІ справді спалить свою обчислювальну потужність і доведе P≠NP, це буде найдосконалішим самодоказом цієї проблеми тисячоліття.
Ця стаття походить із публічного акаунта WeChat «Xinzhiyuan», автор: ASI Revelation
