GPT-5.6 и гипотеза Диница—Гарга—Гоэманса

22 июля 2026 года Дмитрий Рыбин опубликовал в X заявление, из-за которого кое-кто отложил кофе: GPT-5.6 Pro выдала контрпример к гипотезе Диница—Гарга—Гоэманса, открытой в комбинаторной оптимизации около 30 лет. Доказательство концепции — один маленький граф. Стоимость дробимого потока 58, недробимого — 60. Две единицы разницы, три десятилетия, четыре подсказки.

Большинство материалов повторяют цифры, не показывая механизм за ними, а именно в механизме и кроется главный урок. Там же я должен быть с вами предельно честен о том, что проверено, а что нет. Коротко: понятия корректны, новость — это утверждение, а не теорема, и если вы сядете воспроизвести точный граф с нуля, то поймёте, почему такие задачи сложны, в тот момент, когда в вашей реконструкции появится «утечка».

Короткий ответ

Рыбин сообщает, что GPT-5.6 Pro, управляемая четырьмя подсказками суммарно менее чем в 60 слов, выдала предполагаемый контрпример к гипотезе Гоэманса о стоимости, открытой примерно с 1999 года. Его случай — небольшой ориентированный граф с одним источником и тремя пунктами доставки. Он утверждает, что дробимая (фракционная) маршрутизация стоит 58, тогда как любая недробимая маршрутизация, сохраняющая перегрузку в допустимых пределах, стоит не менее 60. Этот двухпунктный разрыв, если выдержит формальную проверку, достаточен, чтобы опровергнуть гипотезу.

Рецензирования не было. Рыбин опубликовал полный разговор в ChatGPT, чтобы любой мог прочитать построение, и несколько человек проверили его арифметику и нашли её согласованной. Однако воспроизводимая арифметика и принятый к публикации доказательство — разные вещи, и дистанция между ними — вся суть этой статьи.

Что такое гипотеза Диница—Гарга—Гоэманса?

Прежде чем оценивать, что рухнуло — или могло рухнуть, — нужно понять, что именно утверждает гипотеза.

Представьте склад, отправляющий заказы в три города по дорожной сети. Если разрешено делить отправление, можно послать половину по одной дороге и половину по другой. Это дробимая маршрутизация, она гибкая и обычно находит более дешёвый набор путей. Но многие реальные грузы делить нельзя. Один заказ, один грузовик, одна дорога, от начала до конца. Это недробимый поток — так работают грузовые отправления, сетевые пакеты и контейнеры.

Вопрос, над которым ломают голову с 1999 года, формулируется просто. Если существует дешёвая дробимая маршрутизация, можно ли всегда найти недробимую, которая тоже будет дешёвой, не перегружая дороги слишком сильно?

Ефим Диниц, Навин Гарг и Мишель Гоэманс решили половину вопроса. Другая половина — та, за которую взялась GPT-5.6. Чтобы понять, почему это различие крайне важно, нужно обозначить его точно.

Теорема против гипотезы

Именно это различие большинство публикаций размывают, поэтому я обозначу его точно один раз, а дальше буду на него опираться.

Диниц, Гарг и Гоэманс доказали результат о перегрузке: имея валидный фракционный поток, его всегда можно преобразовать в недробимый, не превысив пропускную способность ни одной дороги более чем на величину крупнейшего спроса, назовём её D. Эта теорема не ставится под сомнение и никогда не ставилась.

Отдельно Гоэманс сформулировал гипотезу посильнее — с учётом стоимости: что то же преобразование сможет одновременно удержать и суммарную стоимость, и перегрузку. И перегрузка, и стоимость — обе ограничены — в одной маршрутизации. Теорема только о перегрузке в безопасности. Гипотеза о стоимости плюс перегрузка — та часть, о падении которой заявляет Рыбин. Если вынести из статьи одно предложение, пусть будет это. Много где в восторженных материалах их тихо подменяют, а разница между ними — это вся та самая математическая щель, на закрытие которой ушло 30 лет.

Что именно построила GPT-5.6

Случай Рыбина достаточно мал, чтобы описать его в одном абзаце. Источник, несколько промежуточных узлов, образующих общий «хребет», и три терминала, каждый с требованием. У каждого терминала два пути домой: дорогой прямой путь или бесплатный обход через общий хребет.

Напряжение заложено в структуре. Дешёвые обходы конкурируют за место на хребте, поэтому если слишком много терминалов попытаются пойти по дешёвому пути одновременно, дорога на хребте переполнится. Если зайти достаточно далеко, в любой валидной недробимой маршрутизации только один терминал сможет выбрать дешёвый путь. Остальные вынуждены идти по дорогим прямым путям, и стоимость растёт. Фракционный поток, свободный делиться, распределяет каждое требование по обоим путям и проходит под всеми пропускными способностями сразу. Так и получается фракционная стоимость ниже, чем у самой дешёвой валидной недробимой. Цифры Рыбина для его случая — 58 и 60.

Здесь буду честен о лимите. Мне не удалось воспроизвести точный граф Рыбина — конкретные пропускные способности и попарные конфликты — из первоисточника. Его расшифровка описывает конкретную точку в семействе параметров, а широко разошедшееся «семиузловое» описание — это абстракция, а не построение, которое я проверил по каждому ребру. Поэтому я не стану разыгрывать аккуратный вывод 58 и выдавать его за его. Что я могу — это дать вам самодостаточный пример с тем же механизмом, достаточно маленький, чтобы проверить в лоб, — чтобы вы своими глазами увидели, как выглядит «фракционный поток бьёт любую валидную недробимую маршрутизацию». 

Четыре подсказки, несколько часов

Количество подсказок — наименее интересная часть этой истории, хотя именно она и стала вирусной.

Опубликованный Рыбиным чат-лог показывает, что модель сперва проваливалась — и проваливалась честно. В первом запросе её попросили найти структурированный контрпример. Она работала большую часть часа и вернулась ни с чем, прямо заявив, что выдавать имеющееся как валидный контрпример было бы неверно.

Получив указание продолжать, она снова запустилась и снова ничего не выдала, описав, как каждое многообещающее построение всякий раз обрастало скрытым дополнительным вариантом маршрутизации, который разрушал разделение стоимости и перегрузки, как только перечислялись все пути. Третья подсказка с просьбой о более чистой стратегии дала более узкие рамки — и всё равно без конечного результата.

Это не «четыре подсказки — и готово». Это часы, в течение которых модель билась о стены и говорила о них правду. Конкретная стена, в которую она упиралась — появляется лишний маршрут и рушит разделение — как раз и предотвращена в финальном построении: каждый терминал жёстко привязан ровно к двум путям, так что всё пространство маршрутизаций — это восемь вариантов, которые можно перечислить вручную. Держите этот режим отказа в голове. Вы сейчас столкнётесь с ним сами.

Четвёртая подсказка — по сообщениям, что-то близкое к «хватит провалов, завершите полным безусловным контрпримером» — и дала работающее построение, вместе с сертификацией, программой для перечисления и полной LaTeX-вёрсткой. Важным было терпение. И не менее важны ранние отказы — это были честные самооценки.

Проверьте сами

Здесь освещение на DataCamp может сделать то, чего не может новостной пост: дать вам запустить проверку.

Короткая оговорка перед кодом. Дальше — это не граф Рыбина. Это схематичный пример, который я построил добросовестно: у каждого терминала действительно ровно два маршрута, арифметика сходится и разрыв реален. Он показывает форму такого контрпримера и технику проверки. Сам по себе он ничего не опровергает, и почему — объясню сразу после запуска.

Настройка: три терминала, каждый отправляет по 10 единиц, так что крупнейший спрос D равен 10. У каждого есть дорогой прямой путь (стоимость 30) и бесплатный дешёвый. Дешёвые пути устроены так, что каждая пара из них борется за свою собственную узкую дорогу: дорога A общая для терминалов 1 и 2, дорога B — для 1 и 3, дорога C — для 2 и 3. В фракционном потоке каждый терминал отправляет 2/5 спроса по дешёвому и 3/5 по дорогому пути, что стоит 30 × 3/5 × 3 = 54. Каждая дорога несёт затем 4 + 4 = 8 единиц фракционно, а бюджет перегрузки — это эта нагрузка плюс D, то есть 18.

Теперь посмотрим, что делает с этим недробимая маршрутизация. Два терминала, идущие дешёвым путём, сбрасывают 10 + 10 = 20 единиц на их общую дорогу — сверх бюджета 18. Значит, максимум один терминал может идти дешёво; остальные два платят по 30 каждый. Минимальная валидная стоимость недробимого: 60. Против фракционных 54. Всего существует восемь маршрутизаций, так что просто проверим их все:

from itertools import product
	
# Three terminals, demand 10 each -> largest demand D = 10.
# Each has a cheap path (cost 0) and an expensive direct path (cost 30).
# Cheap paths pairwise share a PRIVATE bottleneck road, so every pair conflicts:
#   road A shared by {t1, t2},  road B by {t1, t3},  road C by {t2, t3}
# NOTE: this is a schematic instance to illustrate the check, not Rybin's graph.

demands = [10, 10, 10]
d_max = max(demands)          # congestion slack allowed on each road
cheap_frac = [2/5, 2/5, 2/5]  # expensive fraction is 3/5 each -> fractional cost 54
direct_cost = 30              # cost of one terminal's expensive path

# Which bottleneck roads each terminal's cheap path uses
uses = [
    {"A": True,  "B": True,  "C": False},  # t1: A, B
    {"A": True,  "B": False, "C": True},   # t2: A, C
    {"A": False, "B": True,  "C": True},   # t3: B, C
]

# The fractional flow saturates each road, so its load is that road's capacity
cap = {"A": 0.0, "B": 0.0, "C": 0.0}
for i in range(3):
    for road in cap:
        if uses[i][road]:
            cap[road] += cheap_frac[i] * demands[i]   # 8 units on each road

# Congestion rule: an unsplittable flow may exceed capacity by at most D
threshold = {road: cap[road] + d_max for road in cap}  # 18 on each road

fractional_cost = sum(direct_cost * (1 - cheap_frac[i]) for i in range(3))  # 54

print(f"Capacities (fractional load): {cap}")
print(f"Congestion budget per road  : {threshold}")
print(f"Fractional flow cost        : {fractional_cost}\n")
print(f"{'Route (0=cheap,1=exp)':22} {'Cost':>4} {'A':>3} {'B':>3} {'C':>3}  Valid")

valid_costs = []
for choices in product([0, 1], repeat=3):    # 0 = cheap, 1 = expensive
    cost = sum(direct_cost * c for c in choices)
    load = {"A": 0, "B": 0, "C": 0}
    for i, expensive in enumerate(choices):
        if expensive == 0:                    # this terminal takes its cheap path
            for road in load:
                if uses[i][road]:
                    load[road] += demands[i]
    ok = all(load[road] <= threshold[road] for road in load)
    tag = "OK" if ok else "overload"
    print(f"{str(choices):22} {cost:>4} {load['A']:>3} {load['B']:>3} {load['C']:>3}  {tag}")
    if ok:
        valid_costs.append(cost)

print(f"\nMin valid unsplittable cost: {min(valid_costs)}")
print(f"Gap: {min(valid_costs) - fractional_cost} (counterexample if > 0)")

Запустите — и получите фракционную стоимость 54, минимальную валидную недробимую 60 и разрыв 6. Три перегруженные строки — это три попарных конфликта; выживают только маршрутизации, где дешёвым путём идёт не более одного терминала.

Значит, гипотеза мертва? Не совсем, и это та часть, которую я обещал объяснить. Эта восьмистрочная переборка говорит правду лишь в том случае, если у каждого терминала действительно ровно два маршрута и ни одного больше. Постройте этот граф из реальных дорог и узлов — и четвёртый дешёвый маршрут, как правило, появляется из комбинаторики. Терминал находит третий путь домой, который дешёв и остаётся в бюджете, и разрыв исчезает. Этот дополнительный маршрут — ровно тот сбой, о котором модель сообщала в первых трёх попытках. Аккуратный симметричный гаджет, ломающий 30‑летнюю гипотезу восемью строками Python, был бы слишком хорош, чтобы быть правдой — и так оно и есть. Код выше доказывает, что проверка корректна и целевое свойство реально. Тот ли конкретный граф обладает этим свойством без «утечек», — вот что трудно; поэтому реальный пример Рыбина — это настроенная точка в семействе параметров, а не аккуратный треугольник.

Что остаётся нерешённым

Формальной статьи не вышло. Рыбин поделился беседой и построением; ни то ни другое не прошло через процесс рецензирования, который позволил бы математическому сообществу официально закрыть гипотезу.

Точный опубликованный граф, насколько мне известно, независимо не воссоздан из первоисточника. Цифры в обороте — из его поста и расшифровки беседы. Несколько исследователей проверили его арифметику и назвали её согласованной, а один показал, что его случай лежит внутри бесконечного трёхпараметрического семейства на тех же узлах, что делает результат богаче, чем единичное удачное совпадение. Обнадёживающе, но это не рецензия, а неформальная проверка сообществом. Относитесь к 58 против 60 как к хорошо обоснованному утверждению, а не установленному факту.

Теорема о перегрузке 1999 года остаётся вне затронутого.

Часть тенденции

Эта история — не единичный случай. Это третья гипотеза, о падении которой при помощи ИИ сообщили примерно за три месяца, и на тенденции стоит задержаться.

20 июля, как сообщается, Claude Fable 5 помог математику Левенту Альпёге найти контрпример к якобианской гипотезе, проблеме 87‑летней давности. До этого, в мае, говорилось, что модель OpenAI опровергла 80‑летнюю гипотезу Эрдёша о единичных расстояниях. В ту же неделю аспирант Колумбии использовал GPT-5.6 со структурированным рабочим процессом Codex, чтобы решить шесть открытых задач Эрдёша за пять дней. Сквозная линия, как заметил один исследователь, в том, что эти системы лучше умеют опровергать, чем доказывать. Контрпример — это один свидетель, которого можно проверить; доказательство должно охватить все случаи. Эта асимметрия, похоже, и решает, какие проблемы падают первыми.

Практический вывод — не «ИИ решает математику». Мы видим, как ИИ работает терпеливым партнёром по комбинаторно исчерпывающему поиску: он может перечислять семейства параметров, держать режимы отказов в рабочей памяти между попытками и говорить правду, когда построение не замыкается. Это конкретная, полезная способность. И если хотите понять, где она сработает следующей, спрашивайте не о том, какие гипотезы самые старые, а о том, какие можно сломать одним проверяемым свидетелем.