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, чтобы решить шесть открытых задач Эрдёша за пять дней. Сквозная мысль, как выразился один исследователь, в том, что эти системы лучше умеют опровергать, чем доказывать. Контрпример — это один свидетель, которого можно проверить; доказательство должно охватить все случаи. Эта асимметрия, по‑видимому, и решает, какие проблемы падают первыми.

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