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

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

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

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

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

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

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

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

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

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

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

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

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

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

За словами Вільямса, довговічність ETH призвела до того, що протягом останнього десятиліття його згадували в багатьох наукових статтях, які необхідно буде переглянути, якщо заяви лабораторій штучного інтелекту про їхню неправоту виправдають себе.

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

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

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

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