Коли ШІ наблизився до доведення «гіпотези унікальних ігор», дослідники кинулися випереджати машини

· Наука

Коли ШІ наблизився до доведення «гіпотези унікальних ігор», дослідники кинулися випереджати машини

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

Вранці 11 вересня 2026 року Дор Мінцер отримав повідомлення від друга з питанням, чи близький він до розв’язання однієї з найвідоміших відкритих проблем у теоретичній інформатиці. Мінцер, професор Массачусетського технологічного інституту та провідний експерт із «гіпотези унікальних ігор», спочатку подумав, що це жарт. Потім почали надходити інші повідомлення, і чутки почали складатися в єдину картину. Компанія OpenAI, щойно оголосивши про сенсаційне доведення щодо поведінки рідин, яке сколихнуло математичний світ, нібито знайшла доведення гіпотези унікальних ігор. Можливо, вони оприлюднять результат будь-якого дня. Повідомлення натякали: якщо у Мінцера є власні результати, якими можна поділитися, то зараз саме час це зробити.

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

Мінцер насправді не довів гіпотезу унікальних ігор. Але він та його аспіранти Юмоу Фей і Шуо Ван нещодавно довели результати, що стали віхою для тісно пов’язаної проблеми. Вони перебували в процесі запису своїх висновків — що зазвичай займає місяці або довше, — коли почали ширитися чутки. Тріо поспішило завершити чернетку, щоб їх не затьмарив пресреліз OpenAI. Через три дні, віддавши перевагу повноті перед чіткістю, вони розмістили 95-сторінкову статтю в інтернеті з відмовою від відповідальності на першій сторінці: «Поточна версія рукопису є математично повною, але вона не в тому вигляді, у якому ми хотіли її представити».

Їхнє рішення опублікувати роботу якнайшвидше було швидко виправдане. 6 жовтня OpenAI оголосила про доведення гіпотези унікальних ігор разом із 376 іншими результатами в багатьох галузях математики. Дослідники зустріли потік доведень від ШІ зі змішаним почуттям тривоги та цікавості, яке стало вже звичним після нещодавніх досягнень. Їхня реакція на результат Мінцера була менш суперечливою.

«Він опублікував багато чудових статей на цю тему, — сказав Раян О'Доннелл, дослідник теоретичної інформатики з Університету Карнегі — Меллона. — Це ще одна справді чудова робота».


Майже задоволені

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

Точне розв’язання задач задоволення обмежень може бути важким або навіть неможливим. Іноді існує рішення, що задовольняє кожну умову, але всі відомі методи його пошуку болісно повільні. Або ж обмеження можуть суперечити одне одному, і ідеального рішення просто не існує.

У таких випадках дослідники часто згодні на приблизні рішення, які задовольняють деякі, але не всі умови. Теоретики складності хочуть зрозуміти, чому іноді легко, а іноді важко знайти ці приблизні рішення. «Багато роботи було присвячено спробам зрозуміти, де проходить межа», — каже О'Доннелл.

Гіпотеза унікальних ігор, вперше сформульована у статті 2002 року теоретиком складності Субхашем Хотом, коли він ще був аспірантом, тісно пов’язана з цим пошуком. Вона стосується конкретної задачі задоволення обмежень щодо математичних об’єктів, які називаються графами — це мережі вузлів, з’єднаних лініями, що називаються ребрами. Вам дають граф і просять розфарбувати його вузли, використовуючи фіксовану палітру кольорів. Кожне ребро має правило, яке визначає, якими кольорами мають бути вузли на обох його кінцях. Наприклад, одне конкретне ребро може вимагати, щоб два вузли мали однаковий колір. Інше ребро може вимагати, щоб якщо один вузол червоний, інший обов’язково був синім, а якщо один зелений — інший був жовтим.

Складність цієї задачі розфарбовування залежить від структури графа, кількості дозволених кольорів та конкретного набору обмежень. Хота цікавили випадки, коли найкраще можливе розфарбовування задовольняє більшість, але не всі умови — скажімо, 99%. Знайти таке майже ідеальне розфарбовування — складне завдання. Інтуїтивно здавалося б, що легше знайти розфарбовування, яке задовольняє меншу частку обмежень — 1% або навіть 0,001%.

Гіпотеза унікальних ігор стверджує, що ця інтуїція помилкова. Незалежно від того, наскільки ви готові знизити свої стандарти, завжди знайдуться випадки, коли навіть такі неідеальні розфарбовування важко знайти.

Гіпотеза унікальних ігор висуває разюче твердження, але її справжня цінність полягає у зв’язках з іншими проблемами. Дослідники використовували цю гіпотезу для розв’язання зовсім не пов’язаних питань про геометрію піни та властивості виборчих систем. А у 2008 році інформатик Прасад Рагхавендра довів, що якщо гіпотеза правильна, то один класичний алгоритм є найкращою стратегією для будь-якої задачі задоволення обмежень, де немає ідеального рішення. Ви не можете досягти більшого, експлуатуючи особливості конкретних задач.

Однак у гіпотези є «сліпа пляма». Вона застосовується лише до випадків, де найкраще можливе рішення задовольняє більшість обмежень, як у прикладі з 99%. Вона нічого не говорить про випадки, де є ідеальне рішення, тобто задовольняються 100% обмежень.

Хот з самого початку усвідомлював це обмеження. Щоб розібратися з такими випадками, він визначив варіант задачі унікальних ігор, який назвав задачею 2-до-1 ігор, де обмеження є більш вільними. У початковій задачі розфарбовування вузла на одному боці ребра залишає лише один варіант кольору для іншого боку. У новій версії він дозволив два можливі кольори.

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

У своїй вересневій статті Мінцер та його колеги довели дещо інший варіант другої гіпотези Хота, який має майже такі ж наслідки. Для Мінцера ця робота тривала сім років.


Купа невдач

У 2018 році, ще будучи аспірантом, Мінцер відіграв провідну роль у відомому результаті, що став першим значним кроком до доведення двох гіпотез Хота. Але потім його прогрес застопорився. У 2025 році він обговорив проблему 2-до-1 з Феєм і Ваном, які щойно закінчили перший рік навчання в аспірантурі та завершили плідну першу співпрацю.

«Я дав їм два варіанти задач на вибір, — сказав Мінцер. — Вони були достатньо сміливими, щоб обрати цю».

Щоб вирішити гіпотезу, тріо мало побудувати математичний міст від задачі 2-до-1 до іншої задачі, складність якої вже була добре зрозуміла. У попередній роботі Мінцера перший крок у побудові цього мосту включав трансформацію задачі розфарбовування графів у задачу про «коди, що виправляють помилки» — метод кодування повідомлень, щоб одержувач міг виявляти та виправляти помилки передачі.

Через кілька місяців Фей і Ван визначили багатообіцяючий новий підхід до побудови таких кодів. Але вони не бачили способу поєднати ці нові коди з усіма іншими частинами, які мали увійти в міст.

«Це здавалося дуже далеким, — сказав Мінцер. — Потрібні були дива, щоб усі зірки зійшлися».

Протягом наступних місяців зірки не сходилися. Тріо неодноразово намагалося змусити доведення працювати, але збирання частин до купи відчувалося «як спроба поєднати коло і трикутник у пазлі», — сказав Фей. Проте вони вчилися на кожній невдалій спробі. У квітні 2026 року вони нарешті досягли успіху.

«Ми взяли п’ять невдач і зуміли скріпити цей [новий код] поверх них, — сказав Мінцер. — І тоді все запрацювало».

Технічно Мінцер, Фей і Ван довели дещо слабшу версію гіпотези 2-до-1 ігор Хота, де є чотири варіанти для кожного обмеження замість двох. Але багато наслідків оригінальної гіпотези Хота вже випливали з цієї версії 4-до-1 — найважливішим з них є новий результат про складність класичної задачі розфарбовування графів, яка виникла за десятиліття до робіт Хота. У цій відомій задачі єдиним обмеженням є те, що сусідні вузли не можуть мати однаковий колір. Теоретики складності давно знали, що у випадках, коли граф можна розфарбувати трьома кольорами, знайти таке рішення може бути надзвичайно важко. Новий результат Мінцера, Фея і Вана тепер також означає, що в таких випадках, незалежно від того, скільки додаткових кольорів ви можете використати, завжди знайдуться «неслухняні» графи, для яких розв’язок все одно буде знайти важко.

«Ви не зможете зробити це, навіть маючи цілу коробку Crayola», — сказав Марк Брейверман із Прінстонського університету. Інформатики намагалися довести це десятиліттями — фактично, це була одна з проблем, що спочатку спонукала Хота запропонувати свої гіпотези про розфарбовування графів.

Жовтневий реліз OpenAI включав перевірене за допомогою Lean доведення гіпотези 2-до-1, але в рукописі, згенерованому ШІ, який не пройшов ніякого редагування людьми або перевірки незалежними експертами. Не те щоб результат 4-до-1 за вересень, який поспіхом готували, щоб випередити OpenAI, був у ідеальному стані.

«Починаючи з шостого розділу, буквально немає сполучних слів», — каже Мінцер, лише неперервна послідовність визначень і доведень проміжних результатів. «Ми відчули потребу перепросити за це».

Команда планує опублікувати нову версію своєї статті, коли закінчить її доопрацювання. Але в епоху, коли написання текстів за допомогою ШІ стає повсюдним, цей відверто неопрацьований текст має свою чарівність. Як висловився О'Доннелл: «Вони розв’язали задачу у старий добрий спосіб, своїми розумами, і написали її власними пальцями».


Ціна успіху

А потім є доведення гіпотези унікальних ігор від OpenAI, яке є чим завгодно, але не «старомодним». Це найбільш гучний приклад доведення, згенерованого ШІ в теоретичній інформатиці на сьогодні — і це враховуючи 40 інших доведень, які OpenAI випустила одночасно.

Це забагато для дослідників. «Математика через пресрелізи — це не зовсім здорово для математики», — сказав Брейверман у вересні, коли його запитали про чутки щодо майбутнього оголошення OpenAI. «Ми вже відчуваємо багато невизначеності та неприємностей». Тим не менш, зазначив він, згенероване ШІ доведення гіпотези може відкрити нові напрямки для дослідників. Якщо вони зможуть виокремити ключові припущення в доведенні — що не завжди легко зробити з доведеннями ШІ, — вони зможуть багато чому навчитися, налаштовуючи ці припущення та досліджуючи, як змінюється результат. «Це не означає "зробив і забув"», — сказав він.

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

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

«Ви ж людина, чи не так? Вам потрібно спати, вам потрібно їсти, у вас буває різний настрій, — сказав він. — Ви ніколи не знаєте, чи не випередить вас компанія з трильйонною капіталізацією».

Оригінал: www.quantamagazine.org

Про Що? — новини науки, технологій і світу