GPT-5.6 i hipoteza Dinitza-Garga-Goemansa

22 lipca 2026 r. Dmitry Rybin opublikował na X twierdzenie, które sprawiło, że pewien typ osób odłożył kawę: GPT-5.6 Pro wygenerował kontrprzykład do hipotezy Dinitza-Garga-Goemansa, otwartej w optymalizacji kombinatorycznej od około 30 lat. Dowód koncepcji to mały graf. Koszt przepływu ułamkowego 58, koszt przepływu niedzielonego 60. Dwa punkty, trzy dekady, cztery prompt’y.

Większość relacji powtarza liczby, nie pokazując mechanizmu, który za nimi stoi, a to właśnie w mechanizmie kryje się prawdziwa lekcja. To też miejsce, w którym muszę być z tobą szczery co do tego, co zostało zweryfikowane, a co nie. Krótko: koncepcje są solidne, wiadomość to na razie twierdzenie, a nie twierdzenie matematyczne, i jeśli usiądziesz, by odtworzyć dokładny graf od zera, zrozumiesz, dlaczego takie problemy są trudne w momencie, gdy twoja rekonstrukcja zacznie cieknąć.

Szybka odpowiedź

Rybin podaje, że GPT-5.6 Pro, sterowany czterema promptami o łącznej długości poniżej 60 słów, wygenerował rzekomy kontrprzykład do hipotezy kosztowej Goemansa, problemu otwartego mniej więcej od 1999 r. Przykład to mały graf skierowany z jednym źródłem i trzema terminalami dostaw. Twierdzi, że trasowanie dzielone (ułamkowe) kosztuje 58, podczas gdy każde niedzielone trasowanie utrzymujące przeciążenie w dozwolonym budżecie kosztuje co najmniej 60. Ta różnica dwóch punktów, jeśli przetrwa formalny przegląd, wystarczy, by zatopić hipotezę.

Nie przeszło to procesu recenzji. Rybin opublikował pełną rozmowę z ChatGPT, więc każdy może przeczytać konstrukcję, a kilka osób sprawdziło jego rachunki i uznało je za spójne. Reprodukowalne rachunki i uznany dowód to jednak różne sprawy, a dystans między nimi to cała historia tego artykułu.

Czym jest hipoteza Dinitza-Garga-Goemansa?

Zanim docenimy, co upadło — lub mogło upaść — musimy zrozumieć, co ta hipoteza właściwie mówi.

Wyobraź sobie magazyn wysyłający zamówienia do trzech miasteczek siecią dróg. Jeśli wolno ci podzielić przesyłkę, możesz wysłać połowę jedną drogą, a połowę inną. To trasowanie ułamkowe — elastyczne i zwykle tańsze. Ale wielu prawdziwych ładunków nie da się podzielić. Jedno zamówienie, jedna ciężarówka, jedna droga, od początku do końca. To przepływ niedzielony i właśnie tak musi działać zlecenie przewozowe, pakiet sieciowy czy kontener.

Pytanie, nad którym głowią się od 1999 r., jest proste do sformułowania. Jeśli istnieje tanie trasowanie dzielone, czy zawsze można znaleźć trasowanie niedzielone, które jest również tanie, nie przeciążając dróg zbyt mocno?

Jefim Dinitz, Naveen Garg i Michel Goemans rozstrzygnęli połowę. Druga połowa to ta, na którą rzucił się GPT-5.6. Żeby zrozumieć, dlaczego to rozróżnienie ma kolosalne znaczenie, musimy je precyzyjnie uchwycić.

Twierdzenie kontra hipoteza

To rozróżnienie większość publikacji zaciera, więc wyjaśnię je raz precyzyjnie, a potem będę się do niego odwoływać w reszcie tekstu.

Dinitz, Garg i Goemans udowodnili wynik dotyczący przeciążenia: mając dany poprawny przepływ ułamkowy, zawsze możesz przekształcić go w przepływ niedzielony, nie przekraczając pojemności żadnej drogi o więcej niż największe żądanie, nazwijmy je D. To twierdzenie nie jest kwestionowane i nigdy nie było.

To, co Goemans osobno postulował, to silniejsza, kosztowa wersja: że to samo przekształcenie mogłoby jednocześnie utrzymać w ryzach całkowity koszt. Przeciążenie i koszt — oba ograniczone — w jednym trasowaniu. Twierdzenie tylko o przeciążeniu jest bezpieczne. Hipoteza o koszcie plus przeciążeniu to część, która według Rybina upadła. Jeśli masz zapamiętać z tego tekstu jedno zdanie, niech będzie to właśnie to. Wiele entuzjastycznych relacji po cichu zamienia te dwa wyniki, a różnica między nimi to cała luka matematyczna, której domknięcie zajęło 30 lat.

Co właściwie zbudował GPT-5.6

Przykład Rybina jest na tyle mały, że da się go opisać w jednym akapicie. Źródło, kilka węzłów pośrednich tworzących wspólny „kręgosłup” i trzy terminale, każdy z zapotrzebowaniem. Każdy terminal ma dwie drogi do domu: drogą bezpośrednią, droższą, lub darmowym objazdem przez wspólny kręgosłup.

Napięcie jest strukturalne. Tanie objazdy konkurują o miejsce na kręgosłupie, więc jeśli zbyt wiele terminali naraz próbuje trasować tanio, jedna z dróg kręgosłupa się przepełni. Pchnięte wystarczająco daleko, tylko jeden terminal może wybrać tanią ścieżkę w dowolnym poprawnym niedzielonym trasowaniu. Reszta jest zmuszona do drogich ścieżek bezpośrednich, a koszt rośnie. Przepływ ułamkowy, który może się dzielić, rozkłada każde żądanie na obie ścieżki i mieści się pod każdą pojemnością. Tak właśnie uzyskujesz koszt ułamkowy niższy od najtańszego legalnego kosztu niedzielonego. Liczby Rybina dla jego przykładu to 58 i 60.

Będę szczery co do ograniczenia. Nie byłem w stanie odtworzyć dokładnego grafu Rybina — konkretnych pojemności i konfliktów parami — z pierwotnego źródła. Jego transkrypt opisuje konkretny punkt w rodzinie parametrów, a szeroko udostępniany opis „siedmiu węzłów” jest jego abstrakcją, a nie konstrukcją, którą zweryfikowałem krawędź po krawędzi. Nie będę więc inscenizować zgrabnego wyprowadzenia 58 i udawać, że to jego. To, co mogę zrobić, to dać ci samodzielny przykład pokazujący ten sam mechanizm, mały na tyle, by sprawdzić go metodą siłową, żebyś mógł na własne oczy zobaczyć, jak wygląda „ułamkowy bije każdy legalny niedzielony”. 

Cztery prompt’y, kilka godzin

Liczba promptów jest tu najmniej ciekawa, choć to ona stała się viralem.

Udostępniony przez Rybina log czatu pokazuje, że model najpierw poniósł porażkę — i to uczciwą. Wstępny prompt poprosił o znalezienie strukturalnego kontrprzykładu. Model pracował przez większą część godziny i wrócił z niczym, wprost stwierdzając, że przedstawienie tego, co ma, jako ważnego kontrprzykładu byłoby nieprawdą.

Po poleceniu, by kontynuować, uruchomił się ponownie i znów nic nie znalazł, opisując, jak każda obiecująca konstrukcja dorabiała sobie ukrytą dodatkową opcję trasowania, która niszczyła rozdział koszt–przeciążenie po pełnym wyliczeniu ścieżek. Trzeci prompt z prośbą o czystszą strategię dał węższą ramę i wciąż brak gotowego wyniku.

To nie jest „cztery prompt’y i zrobione”. To godziny modelu uderzającego w ściany i mówiącego o nich prawdę. Konkretna ściana, na którą wciąż wpadał — pojawia się dodatkowa trasa i psuje rozdział — to dokładnie to, czemu finalna konstrukcja zapobiega, przypinając każdy terminal do dokładnie dwóch ścieżek, tak by cała przestrzeń tras to było osiem opcji, które można wypisać ręcznie. Zapamiętaj ten tryb porażki. Za chwilę sam na niego trafisz.

Czwarty prompt, podobno bliski „mam dość twoich porażek, proszę, zakończ kompletnym bezwarunkowym kontrprzykładem”, to ten, który przyniósł działającą konstrukcję wraz z certyfikatami dowodów, programem do enumeracji i pełnym LaTeX-em. Cierpliwość miała znaczenie. Tak samo wcześniejsze odmowy — były uczciwą samooceną.

Sprawdź sam

Tu DataCamp może zrobić coś, czego news nie potrafi: pozwolić ci uruchomić weryfikację.

Szybkie zastrzeżenie przed kodem. To, co poniżej, nie jest grafem Rybina. To schematyczny przykład, który zbudowałem uczciwie: każdy terminal ma naprawdę dokładnie dwie trasy, rachunki się domykają, a luka jest rzeczywista. Pokazuje kształt takiego kontrprzykładu i technikę jego sprawdzania. Sam w sobie niczego nie obala i zaraz wyjaśnię dlaczego — tuż po tym, jak go uruchomisz.

Ustawienie: trzy terminale, każdy wysyła 10 jednostek, więc największe żądanie D to 10. Każdy ma drogą bezpośrednią (koszt 30) i darmową, tanią trasę. Tanie trasy są ułożone tak, że każda para z nich walczy o własną prywatną wąską gardziel: droga A jest współdzielona przez terminale 1 i 2, droga B przez 1 i 3, droga C przez 2 i 3. W przepływie ułamkowym każdy terminal wysyła 2/5 żądania tanio i 3/5 drogo, co kosztuje 30 x 3/5 x 3 = 54. Każda droga niesie wtedy ułamkowo 4 + 4 = 8 jednostek, a budżet przeciążenia to ten ładunek plus D, więc 18.

Teraz zobacz, co robi trasowanie niedzielone. Dwa terminale jadące tanio wrzucają 10 + 10 = 20 jednostek na swoją wspólną drogę — powyżej budżetu 18. Więc co najwyżej jeden terminal może jechać tanio; pozostałe dwa płacą po 30. Minimalny legalny koszt niedzielony: 60. Przy koszcie ułamkowym 54. Istnieje osiem trasowań, więc sprawdzamy wszystkie:

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)")

Uruchomisz i dostaniesz koszt ułamkowy 54, minimalny legalny koszt niedzielony 60 i lukę 6. Trzy przeładowane wiersze to trzy konflikty parami; jedyne dopuszczalne trasowania utrzymują co najwyżej jeden terminal na taniej trasie.

Więc hipoteza martwa? Nie całkiem — i to jest ta część, którą obiecałem wyjaśnić. Ta ośmiowierszowa enumeracja mówi prawdę tylko wtedy, gdy każdy terminal naprawdę ma dwie trasy i ani jednej więcej. Zbuduj ten graf z faktycznych dróg i węzłów, a z kombinatoryki zwykle wyłania się czwarta tania trasa. Terminal znajduje trzeci tani powrót, który mieści się w budżecie, i luka znika. Ta dodatkowa trasa to dokładnie ten błąd, o którym model raportował przy trzech pierwszych próbach. Czysty, symetryczny gadżet, który łamie 30-letnią hipotezę w ośmiu linijkach Pythona, byłby zbyt piękny, by był prawdziwy — i tak właśnie jest. Powyższy kod dowodzi, że sprawdzenie jest poprawne, a badana własność jest realna. To, czy dany graf faktycznie ją ma, bez „wycieków”, jest trudną częścią — i dlatego prawdziwy przykład Rybina to dostrojony punkt w rodzinie parametrów, a nie zgrabny trójkąt.

Co wciąż niewyjaśnione

Nie ukazał się żaden formalny artykuł. Rybin udostępnił rozmowę i konstrukcję; żadna nie przeszła procesu recenzji, który pozwoliłby społeczności matematycznej oficjalnie zamknąć hipotezę.

Dokładny opublikowany graf nie został niezależnie odbudowany z pierwotnego źródła, które mógłbym znaleźć. Krążące liczby pochodzą z jego wpisu i udostępnionego transkryptu. Kilku badaczy sprawdziło jego rachunki i uznało je za spójne, a jeden pokazał, że jego przykład mieści się w nieskończonej trójparametrycznej rodzinie na tych samych węzłach, co czyniłoby wynik bogatszym niż pojedynczy szczęśliwy traf. To zachęcające, ale to nie raport recenzencki, tylko nieformalna kontrola społeczności. Traktuj różnicę 58 vs 60 jako dobrze udokumentowane twierdzenie, a nie ustalony fakt.

Twierdzenie o przeciążeniu z 1999 r. pozostaje nienaruszone.

Część wzorca

Ta historia to nie pojedynczy punkt danych. To trzecia hipoteza, która w ciągu około trzech miesięcy miała upaść przy wsparciu AI, i warto się temu wzorcowi przyjrzeć.

20 lipca Claude Fable 5 podobno pomógł matematykowi Leventowi Alpöge znaleźć kontrprzykład do hipotezy Jacobiego, 87-letniego problemu. Wcześniej, w maju, model OpenAI miał obalić 80-letnią hipotezę Erdősa o odległości jednostkowej. W tym samym tygodniu, co te wieści, doktorant z Columbii użył GPT-5.6 ze strukturalnym workflowem Codex, by rozwiązać sześć otwartych problemów Erdősa w pięć dni. Wspólny motyw, jak ujął to jeden z badaczy, jest taki, że te systemy lepiej radzą sobie z obalaniem niż dowodzeniem. Kontrprzykład to pojedynczy świadek, którego możesz sprawdzić; dowód musi objąć każdy przypadek. Ta asymetria zdaje się decydować, które problemy padają jako pierwsze.

Praktyczna puenta nie brzmi „AI rozwiązuje matematykę”. Obserwujemy AI działającą jako cierpliwy partner od wyczerpujących, kombinatorycznych poszukiwań: taki, który potrafi wyliczać rodziny parametrów, utrzymywać tryby porażek w pamięci roboczej między próbami i mówić prawdę, gdy konstrukcja się nie domyka. To konkretna, użyteczna zdolność. A jeśli chcesz zrozumieć, gdzie uderzy następnie, pytanie nie brzmi, które hipotezy są najstarsze, tylko które da się złamać pojedynczym, sprawdzalnym świadkiem.