GPT-5.6 i hipoteza Dinitza–Garga–Goemansa

22 lipca 2026 r. Dmitry Rybin opublikował na X twierdzenie, po którym 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 jeden mały graf. Koszt przepływu ułamkowego 58, koszt przepływu niepodzielnego 60. Dwa punkty, trzy dekady, cztery prompty.

Większość relacji powtarza liczby, nie pokazując mechanizmu, który za nimi stoi, a to właśnie mechanizm kryje właściwą lekcję. To też miejsce, gdzie muszę z tobą uczciwie omówić, co zweryfikowano, a czego nie. W skrócie: koncepcje są solidne, wiadomość to wciąż twierdzenie nieformalnie zgłoszone, a nie twierdzenie matematyczne, a jeśli usiądziesz, by odtworzyć dokładny graf od zera, zrozumiesz, czemu takie problemy są trudne, w chwili gdy twoja rekonstrukcja zacznie „przeciekać”.

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. Podaje, że trasowanie podzielne (ułamkowe) kosztuje 58, a każde niepodzielne trasowanie, które utrzymuje przeciążenie w dozwolonym budżecie, kosztuje co najmniej 60. Ta różnica o dwa, jeśli przetrwa formalną weryfikację, wystarczy, by obalić hipotezę.

To nie przeszło recenzji naukowej. Rybin opublikował pełną rozmowę z ChatGPT, więc każdy może przeczytać konstrukcję, a kilka osób sprawdziło jego arytmetykę i uznało ją za spójną. Jednak powtarzalna arytmetyka i zaakceptowany dowód to 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 po sieci dróg. Jeśli wolno ci podzielić przesyłkę, możesz wysłać połowę jednym traktem, a połowę innym. To trasowanie ułamkowe, elastyczne; zwykle znajduje tańszy zestaw ścieżek. Ale wiele realnych ładunków podzielić się nie da. Jedno zamówienie, jedna ciężarówka, jedna droga, od początku do końca. To przepływ niepodzielny — i tak działają rzeczywiste zlecenia frachtowe, pakiety sieciowe czy kontenery.

Pytanie rozważane od 1999 r. jest proste do sformułowania. Jeśli istnieje tanie trasowanie podzielne, czy zawsze da się znaleźć trasowanie niepodzielne, które będzie również tanie, nie przeciążając za bardzo dróg?

Jefim Dinitz, Naveen Garg i Michel Goemans rozstrzygnęli połowę. Druga połowa to ta, za którą zabrał się GPT-5.6. Żeby zrozumieć, czemu to rozróżnienie jest ogromnie ważne, trzeba je precyzyjnie ująć.

Twierdzenie kontra hipoteza

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

Dinitz, Garg i Goemans udowodnili wynik o przeciążeniu: mając poprawny przepływ ułamkowy, zawsze można zamienić go na niepodzielny tak, by nie przekroczyć pojemności żadnej drogi o więcej niż największy pojedynczy popyt, nazwijmy go D. To twierdzenie nie jest kwestionowane i nigdy nie było.

Goemans osobno postawił hipotezę silniejszą, uwzględniającą koszt: że ta sama konwersja mogłaby jednocześnie utrzymać niski łączny koszt i niskie przeciążenie. Przeciążenie i koszt, oba ograniczone, w jednym trasowaniu. Twierdzeniu „tylko o przeciążeniu” nic nie grozi. Hipoteza „koszt plus przeciążenie” to ta część, która według Rybina upadła. Jeśli masz z tego tekstu wynieść jedno zdanie, niech będzie to właśnie to. Duża część 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 własnym popytem. Każdy terminal ma dwie drogi do domu: drogą bezpośrednią, drogą drogą, lub darmowym objazdem przez wspólny kręgosłup.

Napięcie jest strukturalne. Tanie objazdy rywalizują o miejsce na kręgosłupie, więc jeśli zbyt wiele terminali naraz spróbuje jechać tanio, jedna z dróg kręgosłupa się przepełni. Jeśli przesuniesz suwak wystarczająco daleko, w każdym poprawnym przepływie niepodzielnym tylko jeden terminal może wybrać tanią trasę. Reszta jest zmuszona na drogie drogi bezpośrednie, a koszt rośnie. Przepływ ułamkowy, swobodny w dzieleniu, rozkłada każdy popyt na obie trasy i mieści się pod każdą pojemnością naraz. Tak uzyskuje się koszt ułamkowy niższy od najtańszego poprawnego kosztu niepodzielnego. Dla swojego przykładu Rybin podaje 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 pierwszorzędnego źródła. Jego transkrypt opisuje konkretny punkt w rodzinie parametrów, a szeroko udostępniany opis „siedmiu węzłów” to jego abstrakcja, nie konstrukcja, którą zweryfikowałem krawędź po krawędzi. Nie będę więc aranżować zgrabnego wyprowadzenia 58 i udawać, że to jego. To, co mogę zrobić, to dać ci samodzielny przykład pokazujący ten sam mechanizm — na tyle mały, by sprawdzić go siłowo — żebyś zobaczył na własne oczy, jak wygląda „ułamkowy wygrywa z każdym legalnym niepodzielnym”. 

Cztery prompty, kilka godzin

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

Udostępniony przez Rybina log czatu pokazuje, że model najpierw zawiódł — i zawiódł uczciwie. Pierwszy prompt poprosił o znalezienie strukturalnego kontrprzykładu. Model pracował przez większą część godziny i wrócił z pustymi rękami, wprost stwierdzając, że przedstawienie tego, co ma, jako ważnego kontrprzykładu byłoby fałszywe.

Po poleceniu, by kontynuował, uruchomił się ponownie i znów nic nie znalazł, opisując, jak każda obiecująca konstrukcja wciąż ujawniała ukrytą dodatkową możliwość trasowania, która niszczyła rozdzielenie koszt–przeciążenie, gdy tylko wyliczyło się wszystkie ścieżki. Trzeci prompt, proszący o czystszą strategię, dał węższe ramy, ale wciąż bez finalnego wyniku.

To nie jest „cztery prompty i zrobione”. To godziny, w których model uderza w ściany i mówi o tym prawdę. Konkretna ściana, na którą wciąż wpadał — pojawia się dodatkowa trasa i psuje rozdzielenie — to dokładnie to, czemu zapobiega finalna konstrukcja, przypinając każdy terminal do dokładnie dwóch ścieżek, tak by cała przestrzeń trasowań to 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 dowodowymi, programem do enumeracji i pełnym LaTeXem. Cierpliwość miała znaczenie. Podobnie wcześniejsze odmowy — były uczciwą samooceną.

Sprawdź samodzielnie

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

Szybka uwaga przed kodem. To, co poniżej, nie jest grafem Rybina. To uczciwy schematyczny przykład, w którym każdy terminal z założenia ma dokładnie dwie trasy, arytmetyka się domyka, a luka jest realna. 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.

Ustawienia: trzy terminale, każdy wysyła 10 jednostek, więc największy popyt D to 10. Każdy ma drogą trasę bezpośrednią (koszt 30) i darmową tanią trasę. Tanie trasy są ułożone tak, że każda para z nich walczy o prywatne wąskie gardło: 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 popytu tanio i 3/5 drogo, co daje koszt 30 × 3/5 × 3 = 54. Każda droga przenosi wtedy 4 + 4 = 8 jednostek ułamkowo, a budżet przeciążenia to ten ładunek plus D, czyli 18.

Teraz zobacz, co z tym robi trasowanie niepodzielne. Dwa terminale jadące tanio wrzucają 10 + 10 = 20 jednostek na swoją wspólną drogę, ponad budżet 18. Więc co najwyżej jeden terminal może pojechać tanio; pozostałe dwa płacą po 30. Minimalny legalny koszt niepodzielny: 60. Dla ułamkowego 54. Istnieje osiem trasowań, więc sprawdzamy każde:

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

Uruchom go, a dostaniesz koszt ułamkowy 54, minimalny legalny koszt niepodzielny 60 i lukę 6. Trzy przeciążone wiersze to trzy konflikty parami; jedyne trasowania, które przechodzą, utrzymują co najwyżej jeden terminal na taniej trasie.

Więc hipoteza martwa? Nie do końca — to ta obiecana część. 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 czwarta tania trasa ma tendencję do pojawiania się z kombinatoryki. Terminal znajduje trzeci tani powrót do domu, który mieszcza się w budżecie, i luka znika. Ta dodatkowa trasa to dokładnie ten błąd, który model raportował w pierwszych trzech 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 jest. Powyższy kod dowodzi, że sprawdzenie jest poprawne, a badana własność realna. Czy dany graf rzeczywiście ma tę własność, bez „wycieków”, to trudna część — i dlatego prawdziwy przykład Rybina to dostrojony punkt w rodzinie parametrów, a nie zgrabny trójkąt.

Co wciąż jest nierozstrzygnięte

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

Nie znalazłem też niezależnej rekonstrukcji dokładnie opublikowanego grafu z pierwszego źródła. Liczby krążące pochodzą z jego posta i udostępnionego transkryptu. Kilku badaczy sprawdziło arytmetykę i uznało ją za spójną, a jeden pokazał, że przykład leży w nieskończonej trójparametrycznej rodzinie na tych samych węzłach, co czyniłoby wynik bogatszym niż pojedynczy szczęśliwy traf. To obiecujące, ale to nie recenzja, tylko nieformalna weryfikacja społeczności. Traktuj 58 kontra 60 jako dobrze uzasadnione twierdzenie, nie ustalony fakt.

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

Część wzorca

To nie jest pojedynczy punkt danych. To trzecia hipoteza, o której doniesiono, że upadła z pomocą AI, w ok. trzy miesiące — i warto się nad tym wzorcem pochylić.

20 lipca Claude Fable 5 miał pomóc matematykowi Leventowi Alpöge znaleźć kontrprzykład do hipotezy Jacobiego, mającej 87 lat. Wcześniej, w maju, model OpenAI rzekomo obalił 80-letnią hipotezę Erdősa o jednostkowych odległościach. W tym samym tygodniu, co ta wiadomość, doktorant z Columbii użył GPT-5.6 ze strukturalnym workflow Codex, by rozwiązać sześć otwartych problemów Erdősa w pięć dni. Wspólny mianownik, jak ujął to jeden z badaczy, jest taki, że te systemy lepiej obalają niż dowodzą. Kontrprzykład to pojedynczy świadek do sprawdzenia; dowód musi objąć każdy przypadek. Ta asymetria zdaje się przesądzać, które problemy upadają najpierw.

Wniosek praktyczny nie brzmi „AI rozwiązuje matematykę”. Oglądamy, jak AI pracuje jako cierpliwy partner w wyczerpującym przeszukiwaniu kombinatorycznym: potrafi wyliczać rodziny parametrów, utrzymywać tryby porażek w pamięci roboczej przez kolejne próby i mówić prawdę, gdy konstrukcja się nie domyka. To konkretna, użyteczna umiejętność. A jeśli chcesz przewidzieć, gdzie uderzy następnie, pytanie nie brzmi, które hipotezy są najstarsze, tylko które można złamać pojedynczym sprawdzalnym świadkiem.