Передові лабораторії ШІ заявляють, що їхні моделі спростували гіпотезу про експоненційний час. Що це означає?

Учора OpenAI оприлюднила розв’язання трьох масштабних математичних задач, які вже давно не давали спокою дослідникам. Одним із них стало несподіване спростування експоненційної часової гіпотези (ETH) — усталеного припущення в інформатиці, яке відіграє значну роль у нашому розумінні того, що складно обчислити.

Як і у випадку з попередніми оприлюдненими доказами від передової лабораторії, наукові спільноти відреагували сумішшю захоплення та розчарування. Математик Anthropic Левент Альпьоге припустив, що OpenAI ґрунтувала свої розв’язання на вже наявних напрацюваннях, а через кілька годин Anthropic оприлюднила власне спростування ETH.

Однак підхід OpenAI змінюється. Цього разу лабораторія по-різному організувала оприлюднення результатів для кожної з трьох залучених дисциплін: математики отримали роботу, опубліковану на GitHub; інформатики сформували робочу групу, попросили оприлюднити докази та профінансувати OpenAI конференцію для їх обговорення; фізики сформували робочу групу, яка визначить, як буде оприлюднено їхній результат.

Професор MIT Раян Вільямс — інформатик, який організовує реакцію своєї галузі на нове відкриття. Вільямс, чия робота зосереджена на питаннях обчислювальної складності, раніше критикував підхід OpenAI, назвавши оприлюднення її доказів на початку цього жовтня «DDOS-атакою на математиків».

Однак він погодився співпрацювати з передовими лабораторіями, щоб допомогти спрямувати ідеї, життєво важливі для галузі, розповів він TechCrunch. Лабораторія попросила його допомогти інтерпретувати розв’язання разом з інформатиками з Каліфорнійського університету в Сан-Дієго Расселом Імпальяццо та Рамамоханом Патурі, які вперше опублікували ETH у 1999 році.

Їхнім першим кроком стала публікація відкритого листа із закликом до науковців, зацікавлених у цих проблемах, надати відгуки та долучитися до обговорення норм щодо внеску ШІ в їхню роботу.

«Деякі частини [доказу OpenAI], можливо, можна назвати рутинними, але є дві чи три частини, які виглядають чужорідними, і саме ці частини змусили мене подумати: вау, над цим усій спільноті потрібно працювати разом», — розповів Вільямс TechCrunch.

Ви за P проти NP?

ETH належить до ширшого класу задач, відомого як P проти NP, який уже десятиліттями привертає увагу інформатики та багатьох інших галузей. Якщо спростити, дослідники намагаються зрозуміти, чи можна будь-яку задачу, розв’язання якої легко перевірити (NP), так само легко розв’язати (P).

Простим прикладом є судоку: коли розв’язання головоломки вже є, його можна швидко перевірити, але пошук розв’язання забирає багато часу. Така закономірність характерна для широкого спектра важливих задач, і це розуміння лежить в основі криптографічних систем: маючи ключ до закодованого повідомлення, його можна розшифрувати, але фактичний злам ефективного коду займає надто багато часу, щоб це було практично корисно.

Однак науковці досі не довели, чи це завжди так. «P = NP означає, що ви не лише можете перевірити розв’язання судоку, коли вони існують, а й просто згенерувати їх, — сказав Вільямс. — P = NP стверджує, що це справедливо для кожної задачі, яку можна швидко перевірити: якщо її можна швидко перевірити, її можна швидко розв’язати. Тож це просто здається надто хорошим, щоб бути правдою».

Саме тому більшість науковців припускає, що P ≠ NP. ETH надала цьому підтвердження. По суті, вона стверджує, що навіть найшвидшому комп’ютерному алгоритму потрібно експоненційно більше часу, щоб знайти розв’язання, зі зростанням кількості змінних у певному класі складних логічних головоломок.

OpenAI та Anthropic стверджують, що їхні моделі розробили алгоритми, які розв’язують такі головоломки за «субекспоненційний» час, тобто швидше, ніж вважалося можливим раніше. Якщо це правда, вони могли довести хибність ETH — у наукових термінах, спростувати її — і, можливо, відкрити шлях до алгоритмів, які загалом забезпечують P = NP.

«Кожному інформатику, ймовірно, варто трохи більше зважати на правдоподібність P = NP, але міра цієї впевненості може бути різною, — сказав Вільямс. — Я справді думаю, що це певною мірою ставить під сумнів багато інтуїтивних уявлень, які, як нам здавалося, ми мали щодо … того, наскільки розв’язними є [складні задачі NP]. Я також думаю, що це, ймовірно, не остаточна відповідь. Не думаю, що алгоритм OpenAI може бути найкращим алгоритмом із можливих».

Подальша робота для інформатиків

Стійкість ETH призвела до того, що протягом останнього десятиліття її включали до багатьох наукових праць, які доведеться переглянути, якщо твердження лабораторій ШІ про те, що вони спростували її, витримає перевірку, сказав Вільямс.

«Частково саме тому я просив або наполягав, щоб OpenAI підтримала конференцію з цього питання — це вплине на роботу багатьох дослідників, і нам потрібно з’ясувати, що буде далі. Окрім розуміння алгоритмів, нам потрібно зрозуміти, якими мають бути засади, на які ми раніше спиралися», — сказав він.

До наукових проблем додаються питання кібербезпеки. Вільямс сказав, що вдосконалений алгоритм може означати, що криптографічні системи, які покладаються на певні розміри ключів, можна буде вважати зламаними. Тож одним із перших запитань, яке він поставив керівнику наукового напряму OpenAI Дену Робертсу, було: «чи перевірили вони, чи впливає це на якісь криптографічні системи … чи є тепер щось незахищеним? І, схоже, вони перевірили й були достатньо впевнені, що це … не означає зламу жодних систем».

Ця нова парадигма наукових відкриттів за допомогою ШІ все ще перебуває в процесі становлення, але Вільямс налаштований оптимістично, попри реальні побоювання, особливо щодо підготовки наступного покоління науковців. Ймовірно, те, що він інформатик і займається математикою високого рівня, полегшило для нього адаптацію порівняно з математиками, які працюють лише в математиці.

Водночас він каже, що ШІ «змушує людей бути трохи амбітнішими щодо роботи, яку вони виконують, і глибше замислюватися: якщо все, над чим я раніше працював, тепер є для ШІ низькоосвисаючим плодом, як мені підняти планку для наукових питань, які я хочу порушувати?»