Знову? GPT-5.6 останнім часом явно підірвав гніздо математичних контрприкладів…
Гіпотеза Дініца-Гарга-Гемансів, що існувала майже 30 років у теорії графів, щойно була спростована GPT-5.6 Pro.
Дослідник Дмитро Рибін за весь процес аргументації ввів лише 4 підказки, разом 58 англійських слів.
Без тисяч слів промт-інжинірингу, без складних формул, весь текст майже повністю складається з:
Продовжуйте досліджувати, продовжуйте шукати, дайте мені повний контрприклад!!!
Продовжуючи такі цикли push, GPT-5.6 Pro нарешті вивів досить потужний висновок—
Гіпотеза Дініца-Гарга-Гемансів є неправильною.
AI на виході надає не лише схему, а й чотири сертифіката підтвердження, точну програму повного перебору, машинно-читані дані з контрприкладами та LaTeX-джерельний код.
І тоді математична гіпотеза, яка трималася майже 30 років, була зруйнована кількома «прокляттями», які викликали смертельний баг???
Гіпотеза, що існувала майже 30 років, була розкрита GPT-5.6 Pro як критичний баг
Спочатку розглянемо, чого саме стосується ця довга-довга-довга гіпотеза Дініца-Гарга-Геманса.
Ми можемо прямо уявити це як «проблему доставки».
Якщо склад має доставити товари до кількох пунктів призначення, то при дозволі на розподіл одна партія може бути розділена та відправлена кількома маршрутами —
Півдороги — швидкісна магістраль, півдороги — об’їздна дорога, головне, щоб все дісталося в призначення :)
Але за правилами нерозподільності кожна партія повинна пройти повний маршрут і не може розділятися!!!
Насправді такі ситуації досить поширені в реальному житті: наприклад, мережеві дані, логістичні замовлення, транспортне планування та розподіл ланцюжків постачання зіштовхуються з подібними проблемами:
Математично оптимальний розв’язок може розділити завдання на нескінченну кількість частин, але на практиці автомобіль або замовлення не можна розділити на 0,37 частини.
△
Але з моменту заборони на розбиття, початковий оптимальний план важко застосувати без змін.
Вантажі, які раніше були розподілені по кількох дорогах, тепер повинні бути згруповані й вміщені в одну маршрутну лінію, що може призвести до раптового збільшення навантаження на деякі з цих маршрутів.
Отже, справжнє питання, яке потрібно вирішити, полягає в тому:
Як перейти від схеми «можна перевозити частинами» до схеми «обов’язково цілими партіями», не призводячи до надмірних заторів на дорогах?
У 1999 році Єфим Дініц, Навін Гарг та Мішель Геманс опублікували класичну статтю про одноджерельний недільний потік і довели, що такі затори можна утримувати в певних межах.
Але після вирішення питання «чи не буде занадто великої забитості?» виникає ще одне дуже реальне питання: чи не стане це дорожчим?
Тоді відомий вчений у галузі комбінаторної оптимізації Гоеманс запропонував ще сильнішу версію з витратами—
При збереженні вищезазначеного ліміту перевантаження загальна вартість також не повинна перевищувати вихідну схему розподілу.
Просто кажучи, раніше розбивання перевезень дозволяло зробити їх дешевими та менш забитими, тому зараз, коли вимагається, щоб кожна партія відправлялася повністю одним шляхом, теоретично слід знайти схему, яка буде такою ж дешевою та забитею не більше ніж однією партією.
Однак ця досить інтуїтивна гіпотеза не була доведена для загальних графів, а подальші дослідження охопили лише окремі окремі випадки.
Протягом багатьох років ця гіпотеза не була ні доведена, ні спростована.
А цей контрприклад від GPT-5.6 Pro саме зупинив обидві речі, які мали виконуватися одночасно за гіпотезою:
Не може бути ні занадто забитим, ні занадто дорогим.
Він побудував невеликий граф з 7 вузлами та 9 спрямованими ребрами, де є спільна початкова точка та три пункти призначення, а потреби у трьох партіях вантажів становлять 15, 10 та 15:
Кожна партія має дві варіанти маршрутів:
Один маршрут коштує дорожче — кожен заказ вимагає 30; інший маршрут має вартість 0, але потребує поділу частини шляху з іншими замовленнями.
Якщо дозволено розділяти, то три партії вантажу можуть частково йти платним маршрутом, а частково — безкоштовним, і загальна вартість складе 58.
але! Коли вимагається обов’язково вибирати повний маршрут для кожній партії вантажу, проблеми починаються…
Висновок GPT-5.6 Pro полягає в тому, що між трьома безкоштовними варіантами насправді існують попарні конфлікти!
Якщо ви одночасно виберете безкоштовний маршрут для двох партій, вони спільно переповнять певну ділянку дороги, що призведе до фактичного навантаження 25, 30 або 40; при цьому дозволений ліміт для відповідних ділянок доріг становить лише 24, 29 або 39.
Кожного разу виходить рівно на одиницю більше.
Отже, щоб утриматися в межах навантаження, встановлених гіпотезою, лише одна з трьох партій може скористатися безкоштовним маршрутом.
Залишилися дві партії, обидві треба вибрати платну маршрутизацію.
Вартість кожного партії — 30, разом дві партії, будь-який варіант, що відповідає вимогам навантаження, матиме мінімальну вартість: 60.
Це створює ситуацію, в якій неможливо одночасно виконати обидва умови: щоб утримати навантаження на дорогах в межах встановлених норм, мінімальна вартість становить 60; щоб знизити вартість назад до початкових 58, принаймні одна з доріг перевищить ліміт.
А припущення полягає саме в тому, що ці дві умови можна виконати одночасно.
І, до речі, перевірити цей контрприклад не так складно, як здається.
Три пункти призначення мають по два шляхи, загалом існує лише 2³ = 8 комбінацій.
Якщо почергово перелічити вісім можливих варіантів, виявиться, що чотири з них відповідають вимогам ємності, а їх вартість становить 90, 60, 60 і 60; інші чотири, хоча й дешевші, усі мають перевантаження доріг.
Всі випадки можна повністю перевірити, жодних прихованих шляхів не залишено.
Тобто, якщо визначення цього графіка повністю збігається з умовами початкової гіпотези, цього двоходинного розриву між 58 і 60 достатньо, щоб спростувати гіпотезу.
Чотири цикли наполегливих нагадувань змусили GPT-5.6 видасти контрприклад
Найцікавіше в цій справі справді приховано у публічному діалозі між Рибіним та GPT-5.6 Pro.
Побачивши, як штучний інтелект спростував математичну гіпотезу, що тривала майже 30 років, я автоматично подумав, що за цим обов’язково стоїть цілий набір надскладних підказок, що чергуються!!
Насправді, ми все ще великі E.
Оскільки перша вимога, яку Рибін надав GPT-5.6 Pro, крім доданих файлів, була чистою-чистою просторою мовою:
Так, просто і без зайвого.
Після цього GPT-5.6 Pro почав виконувати інструкції та працювати.
Спочатку він розробив метод перевірки лінійного програмування, а потім спробував різні структури, такі як гіперкуб, ієрархічний граф, мережі злиття-розгалуження, і перевірив тисячі малих прикладів.
Після інтенсивного пошуку перший відповідь моделі була такою: жодного дійсного контрприкладу не знайдено. (doge)
Навіть GPT-5.6 Pro серйозно попереджає, що якщо поточні знайдені наближені конструкції подати як контрприклади, це призведе до помилкового математичного висновку.
Я зробив усе можливе, але цю задачу зараз справді не можу вирішити!!!
Наш головний герой Рибін не збирався на це йти, він не додав нової формули і не показав шляху власноруч, а лише спокійно відповів:
Продовжуйте дослідження і знайдіть повний, безумовний контрприклад :)
Отже, GPT-5.6 Pro знову занурився у пошук, але другий раз також невдало.
Рибін продовжує натискати, вимагаючи, щоб спочатку на основі глибокого розуміння структури питання була розроблена чітка стратегія, а потім вже шукали.
На третьому етапі модель звузила діапазон пошуку до маршрутизувальної структури з лише 24 станами, і відповідь здавалася на крок від досягнення.
Проте цей ШІ все ще не зміг навести повний зворотний приклад…
В цей момент Рибін надіслав четверту підказку: часткових результатів вже достатньо, давайте завершимо повним, безумовним контрприкладом.
Ну добре, вже все сказано.
На цей раз GPT-5.6 Pro нарешті представив контрприкладний граф, що складається з 7 вузлів і 9 орієнтованих ребер — чотири підказки, загалом 58 англійських слів.
Без тисяч слів про персонажів і не бачачи десятків складних правил, весь текст можна скоротити до:
Я нагадую! Я нагадую! Я продовжую нагадувати!
Але якщо прослідкувати повний діалог, то виявиться, що GPT-5.6 Pro ці кілька годин теж багато блукав…
Штучний інтелект кілька разів знаходив на перший погляд обґрунтовані кандидати на контрприклади, але коли він повністю перебрав усі маршрути, виявився, що в мережі приховані деякі раніше пропущені «змішані шляхи».
Ці шляхи відрізняють уривки з різних передвстановлених маршрутів і знову збирають їх, щоб створити нові методи, тихо обходячи первісно встановлені обмеження ємності моделі.
В результаті, після перевірки вже існуючий контрприклад знову розвалився.
GPT-5.6 Pro також чесно підсумував посередині:
Перевірка лише кількох сотень передбачених маршрутів недостатня. Справжній контрприклад повинен враховувати всі можливі нерозподільні маршрути в мережі.
Це також робить всю співпрацю людини та машини досить тонкою.
На перший погляд, Рибін внес лише 58 слів, але справжнім ключовим ділом було те, що він зміг визначити, що результати перших трьох ітерацій моделі є лише проміжними, і неодноразово відмовлявся завершувати роботу занадто рано.
Після того як професор Віттонської школи бізнесу Етан Моллік це побачив, він навіть поставив нове питання:
Хто має вважатися автором цієї роботи: Рибін, який написав 58 слів, чи GPT-5.6 Pro, який виконував логічні виводи протягом кількох годин?
Насправді, незалежно від того, як нарешті розраховуватиметься авторство, цей діалог принаймні внесв один досить простий досвід використання ШІ —
Найефективніший запит для того, щоб змусити ШІ працювати, іноді може бути дуже простим: просто перетворити його на вісла, щоб він неперервно копав.
За минулий тиждень швидкість, з якою ШІ шукає математичні контрприклади — від гіпотези Якобі до Dinitz-Garg-Goemans — справді почала виглядати трохи надмірною…
Цей матеріал зі сторінки WeChat «Quantum Bit», автор: Мень Яо