Опять? ?? GPT-5.6 недавно точно наткнулся на гнездо математических контрпримеров…
Гипотеза Диница-Гарга-Геманс, существовавшая в теории графов почти 30 лет, недавно была опровергнута GPT-5.6 Pro.
Исследователь по имени Дмитрий Рыбин за весь процесс аргументации ввел всего 4 подсказки, в сумме 58 английских слов.
Без тысяч слов промпт-инжиниринга, без сложных формул, почти полностью состоит из:
Продолжайте исследовать, продолжайте искать, дайте мне полный контрпример!!!
Продолжая такую серию запросов, GPT-5.6 Pro действительно выдал довольно ошеломляющий вывод—
Гипотеза Диница-Гарга-Геманса неверна.
В финальной поставке от ИИ, помимо схемы, содержатся четыре сертификата подтверждения, программа точного исчерпывающего проверки, машиночитаемые данные контрпримеров и исходный код LaTeX.
Итак, математическая гипотеза, державшаяся почти 30 лет, была разрушена всего несколькими «приговорами»?
Гипотеза, существовавшая почти 30 лет, была опровергнута GPT-5.6 Pro из-за смертельного бага
Сначала давайте разберемся, чем именно занимается эта длинная-предлинная гипотеза Диница-Гарга-Геманса.
Мы можем представить это как «проблему доставки».
Предположим, что склад должен доставить груз на несколько пунктов назначения; при разрешении разделения одна партия груза может быть разделена и отправлена по нескольким маршрутам —
Половина по скоростной, половина объездом по федеральной трассе — главное, чтобы всё доставили вовремя～
В соответствии с правилами неделимости, каждая партия груза должна пройти полный маршрут целиком, разделять нельзя!!!
На самом деле такие ситуации в реальной жизни встречаются довольно часто — например, при работе с сетевыми данными, логистическими заказами, транспортным расписанием и распределением цепочек поставок.
Математически оптимальное решение может разделить задачу на бесконечно малые части, но в реальности автомобиль или заказ нельзя разделить на 0,37 части.
△
А как только разделение запрещено, исходный оптимальный вариант сложно применить напрямую.
Грузы, ранее распределенные по нескольким маршрутам, теперь должны быть сжаты в одну единственную линию, и нагрузка на некоторые маршруты может внезапно возрасти.
Таким образом, настоящая проблема, которую нужно решить, заключается в том, что:
Как изменить схему «можно перевозить частями» на «обязательно перевозить полностью», не вызывая при этом чрезмерных пробок на дорогах?
В 1999 году Ефим Диниц, Навин Гарг и Мишель Геманс опубликовали классическую статью по области однократного неделимого потока и доказали, что такие заторы можно контролировать в определенных пределах.
Но если решена проблема «не станет ли слишком загруженным», возникает еще один очень реальный вопрос: не станет ли это дороже?
Таким образом, известный ученый в области комбинаторной оптимизации Гоеманс предложил более сильную версию с учетом затрат —
При сохранении вышеуказанного предела перегрузки общая стоимость также не должна превышать стоимость исходной схемы распределения.
Проще говоря, раньше при раздельной перевозке удавалось добиться низкой стоимости и минимальных заторов; теперь, когда требуется, чтобы каждая партия груза проходила по одному полному маршруту, теоретически также следует найти решение с такой же низкой стоимостью и задержками не более чем для одной партии.
Однако эта интуитивно понятная гипотеза до сих пор не была доказана для общих графовых структур; последующие исследования смогли доказать лишь некоторые частные случаи.
В последующие годы эта гипотеза ни доказана, ни опровергнута.
А контрпример, предоставленный GPT-5.6 Pro, как раз блокирует оба условия, которые должны выполняться одновременно согласно гипотезе:
Не должно быть слишком загружено и не должно стать дороже.
Он построил небольшой граф с 7 узлами и 9 направленными ребрами, имеющий одну общую точку отправления и три пункта назначения, при этом спрос на три партии грузов составляет 15, 10 и 15:
Каждая партия имеет два варианта маршрута:
Один маршрут стоит дороже — на завершение каждого заказа уходит 30; другой маршрут бесплатный, но требует совместного использования части дороги с другими заказами.
Если разрешено разделение, то три партии груза могут частично следовать по платному маршруту, а частично — по бесплатному, в итоге общая стоимость составит 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», автор: Мэн Яо