GPT-5.6 ve Dinitz-Garg-Goemans Varsayımı

22 Temmuz 2026’da Dmitry Rybin, belirli bir kitlenin kahvesini masaya bırakmasına neden olan bir iddiayı X’te paylaştı: GPT-5.6 Pro, yaklaşık 30 yıldır kombinatoryal optimizasyonda açık olan Dinitz-Garg-Goemans varsayımına bir karşı-örnek üretmişti. Kanıt fikri küçük bir grafikti. Kesirli akış maliyeti 58, bölünemez akış maliyeti 60. İki puan, üç on yıl, dört komut.

Çoğu haber, sayıların arkasındaki mekanizmayı göstermeden bu rakamları tekrar ediyor; oysa asıl ders mekanizmanın içinde. Ayrıca, nelerin doğrulandığı ve nelerin doğrulanmadığı konusunda size açık olmam gereken yer de burası. Kısa versiyon: kavramlar sağlam, haber bir iddia ve henüz teorem değil; ve sıfırdan tam olarak aynı grafiği yeniden üretmeye oturduğunuzda, yeniden kurduğunuz yapı sızdırmaya başladığı anda bu tür problemlerin neden zor olduğunu öğreniyorsunuz.

Hızlı Yanıt

Rybin, toplamda 60 kelimenin altında dört komutla yönlendirilen GPT-5.6 Pro’nun, yaklaşık 1999’dan beri açık olan Goemans’ın maliyet varsayımına bir karşı-örnek ürettiğini bildiriyor. Örneği, tek bir kaynak ve üç teslim terminali olan küçük bir yönlü grafik. Bölünebilir (kesirli) yönlendirmenin maliyetinin 58, izin verilen tıkanıklık bütçesi içinde kalan herhangi bir bölünemez yönlendirmenin maliyetinin ise en az 60 olduğunu belirtiyor. Bu iki puanlık fark, resmi incelemeden sağ çıkarsa, varsayımı batırmaya yeter.

Hakemli değerlendirmeden geçmedi. Rybin, herkesin inşayı okuyabilmesi için tüm ChatGPT konuşmasını yayınladı ve birkaç kişi aritmetiğini kontrol edip tutarlı buldu. Ancak tekrarlanabilir aritmetik ile kabul görmüş bir ispat farklı şeylerdir; aralarındaki mesafe ise bu makalenin tüm hikâyesidir.

Dinitz-Garg-Goemans Varsayımı Nedir?

Ne düştü — ya da düşmüş olabilir — anlayabilmek için önce varsayımın ne dediğini bilmemiz gerekir.

Bir deponun bir yol ağı üzerinden üç kasabaya sipariş gönderdiğini hayal edin. Bir sevkiyatı bölmenize izin verilirse, bir siparişin yarısını bir yoldan, diğer yarısını başka bir yoldan gönderebilirsiniz. Bu, kesirli yönlendirmedir ve esnektir; genellikle daha ucuz bir yol kümesi bulur. Ancak gerçek yüklerin çoğu bölünemez. Bir sipariş, bir kamyon, bir yol, baştan sona. Bu da bölünemez akıştır ve bir yük emrinin, bir ağ paketinin ya da bir konteynerin gerçekte yapmak zorunda olduğu şeydir.

1999’dan beri üzerinde düşünülen soru ifade olarak basit. Ucuz bir bölünebilir yönlendirme varsa, yollara çok fazla yük bindirmeden aynı zamanda ucuz olan bir bölünemez yönlendirme her zaman bulunabilir mi?

Yefim Dinitz, Naveen Garg ve Michel Goemans bunun yarısını çözdü. Diğer yarısı, GPT-5.6’nın hedef aldığı kısımdı. Bu ayrımın neden son derece önemli olduğunu anlamak için buna tam olarak açıklık getirmemiz gerekiyor.

Teorem ve Varsayım

Bu, çoğu yazının belirsiz bıraktığı ayrım; o yüzden bir kez netleştireceğim ve makalenin kalanında buna dayanacağım.

Dinitz, Garg ve Goemans bir tıkanıklık sonucunu ispatladı: Geçerli bir kesirli akış verildiğinde, her yolun kapasitesini en büyük tekil talep kadar (bu sayıya D diyelim) aşmadan her zaman bölünemez bir akışa dönüştürebilirsiniz. Bu teorem tartışmalı değildir ve hiç olmadı.

Goemans’ın ayrı olarak öne sürdüğü ise daha güçlü, maliyet odaklı versiyondu: aynı dönüşümün tıkanıklığı sınırlarken toplam maliyeti de düşük tutabileceği. Tıkanıklık ve maliyet, ikisi birden, tek bir yönlendirmede sınırlı. Yalnızca tıkanıklık teoremi güvende. Maliyet artı tıkanıklık varsayımı ise Rybin’in düştüğünü söylediği parça. Bu yazıdan bir cümle aklınızda kalacaksa, o bu olsun. Heyecanlı haberlerin çoğu ikisini sessizce yer değiştiriyor; aralarındaki fark, kapanması 30 yıl alan tüm matematiksel boşluğun kendisi.

GPT-5.6 Gerçekte Ne İnşa Etti?

Rybin’in örneği bir paragrafta anlatılacak kadar küçük. Bir kaynak, ortak bir “omurga” oluşturan birkaç ara düğüm ve her biri bir talep taşıyan üç terminal. Her terminalin eve dönmenin iki yolu var: pahalı bir doğrudan yol ya da ortak omurga üzerinden ücretsiz bir dolambaç.

Gerginlik yapısal. Ucuz dolambaç yollar omurgadaki alan için rekabet ediyor; aynı anda çok fazla terminal ucuz yönlendirmeyi denerse omurga üzerindeki bir yol taşıyor. Bunu yeterince zorlarsanız, geçerli herhangi bir bölünemez yönlendirmede yalnızca bir terminal ucuz yolunu kullanabilir. Geri kalanlar pahalı doğrudan yollarına zorlanır ve maliyet yükselir. Serbestçe bölünebilen kesirli akış ise her talebi her iki yola da yayar ve tüm kapasite sınırlarının altından süzülür. “Kesirli maliyetin, en ucuz yasal bölünemez maliyetin altına inmesi” böyle olur. Rybin’in örneği için rakamlar 58 ve 60.

Burada bir sınır konusunda dürüst olacağım. Birincil bir kaynaktan Rybin’in tam grafiğini, belirli kapasite ve ikili çatışmaları yeniden üretemedim. Transkripti, bir parametre ailesindeki belirli bir noktayı anlatıyor ve yaygın paylaşılan “yedi düğüm” betimi bunun soyutlaması; kenar kenar doğruladığım bir kurulum değil. Bu yüzden 58’in pürüzsüz bir türetimini sahneleyip sanki onunkiymiş gibi davranmayacağım. Yapabileceğim şey, aynı mekanizmayı gösteren, kaba kuvvetle kontrol edilecek kadar küçük, kendi kendine yeten bir örnek vermek; böylece “kesirli, her yasal bölünemezi geride bırakıyor” ifadesinin gözle görülür halini kendiniz görebilirsiniz. 

Dört Komut, Birkaç Saat

Komut sayısı bu hikâyenin en az ilginç kısmı, ama viral olan kısmı da o.

Rybin’in paylaştığı sohbet kaydı, modelin önce başarısız olduğunu ve bunu doğru tespit ederek başarısız olduğunu gösteriyor. Açılış komutu ondan yapılandırılmış bir karşı-örnek bulmasını istedi. Yaklaşık bir saat çalıştı ve elindekini geçerli bir karşı-örnek olarak sunmanın yanlış olacağını açıkça belirterek eli boş döndü.

Devam etmesi söylenince tekrar çalıştı ve yine bir şey bulamadığını bildirdi; her umut vaat eden inşanın, tüm yollar sayıldığında maliyet-tıkanıklık ayrımını bozan gizli bir ek yönlendirme seçeneği çıkardığını anlattı. Daha temiz bir strateji isteyen üçüncü komut, daha dar bir çerçeve sağladı ama yine bitmiş bir sonuç yoktu.

Bu, “dört komut, bitti” değil. Bu, bir modelin saatlerce duvara toslayıp bunun hakkında doğruyu söylemesi. Sürekli tosladığı belirli duvar — ekstra bir yol beliriyor ve ayrımı mahvediyor —, nihai inşanın tam da bunu engellemek için her terminali tam iki yola sabitleyerek, tüm yönlendirme uzayını elde elle sayılabilir sekiz seçeneğe indirerek yaptığı şey. Bu başarısızlık biçimini aklınızda tutun. Birazdan siz de onunla karşılaşacaksınız.

Dördüncü komutun, bildirildiğine göre “artık yeter, lütfen eksiksiz ve koşulsuz bir karşı-örnekle bitir” gibi bir şeye yakın olduğu, çalışan inşayı ürettiği; bununla birlikte ispat sertifikaları, bir sayım programı ve tam LaTeX çıktısı verdiği söyleniyor. Sabır önemliydi. Önceki geri çevirmeler de öyle; bunlar dürüst öz değerlendirmelerdi.

Kendiniz Kontrol Edin

İşte DataCamp kapsamının bir haber yazısının yapamayacağı bir şeyi yapabileceği yer: doğrulamayı çalıştırmanıza izin vermek.

Koda geçmeden önce hızlı bir uyarı. Aşağıdaki Rybin’in grafiği değil. Bu, dürüst olmak için kurduğum şematik bir örnek; her terminalin tam olarak iki güzergâhı gerçekten var, aritmetik kapanıyor ve fark gerçek. Böyle bir karşı-örneğin şeklini ve bir tanesini kontrol etme tekniğini gösteriyor. Kendi başına hiçbir şeyi çürütmez; nedenini kodu çalıştırdıktan hemen sonra açıklayacağım.

Kurulum: üç terminal, her biri 10 birim sevk ediyor; dolayısıyla en büyük talep D, 10. Her birinin pahalı bir doğrudan yolu (maliyeti 30) ve ücretsiz ucuz bir yolu var. Ucuz yollar öyle düzenlenmiş ki her ikili kombinasyon kendi özel dar boğaz yolunda çatışıyor; A yolu 1 ve 2 terminallerince, B yolu 1 ve 3, C yolu 2 ve 3 tarafından paylaşılıyor. Kesirli akışta, her terminal talebinin 2/5’ini ucuza, 3/5’ini pahalıya gönderiyor; bu da 30 x 3/5 x 3 = 54’e mal oluyor. Her yol böylece kesirli olarak 4 + 4 = 8 birim taşıyor ve tıkanıklık bütçesi bu yük artı D, yani 18.

Şimdi bölünemez yönlendirmenin buna ne yaptığını izleyin. İki terminalin birden ucuza gitmesi, paylaşılan yollarına 10 + 10 = 20 birim yük bindirir ve bu 18’lik bütçeyi aşar. Dolayısıyla en fazla bir terminal ucuz yönlendirme yapabilir; diğer ikisi 30’ar öder. Asgari yasal bölünemez maliyet: 60. Kesirli ise 54. Sekiz yönlendirme vardır; hepsini kontrol ederiz:

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

Çalıştırdığınızda 54’lük bir kesirli maliyet, 60’lık asgari yasal bölünemez maliyet ve 6’lık bir fark elde edersiniz. Aşırı yüklenmiş üç satır, üç ikili çatışmadır; hayatta kalan tek yönlendirmeler en fazla bir terminali ucuza tutar.

O halde varsayım öldü mü? Henüz değil; söz verdiğim kısım da bu. Bu sekiz satırlık sayım ancak her terminalin gerçekten iki güzergâhı ve daha fazlası olmadığı durumda doğruyu söyler. Bu grafiği gerçek yollar ve düğümlerden kurduğunuzda, kombinatorikler içinden dördüncü bir ucuz yol belirme eğilimindedir. Bir terminal, bütçe altında kalan üçüncü bir ucuz dönüş yolu bulur ve fark kapanır. Bu ek yol, modelin ilk üç denemede bildirdiği hatanın ta kendisi. Sekiz satır Python ile 30 yıllık bir varsayımı bozan temiz, simetrik bir düzenek kulağa gerçek olamayacak kadar iyi geliyor — ve öyle. Yukarıdaki kod, kontrolün sağlam olduğunu ve hedef özelliğin gerçek olduğunu ispat eder. Belirli bir grafiğin gerçekten bu özelliğe sızma olmadan sahip olup olmadığını bulmak ise zor olan kısımdır; ve bu, Rybin’in gerçek örneğinin düzenli bir üçgen yerine bir parametre ailesinde ayarlanmış bir nokta olmasının nedenidir.

Hâlâ Çözümlenmemiş Olanlar

Resmî bir makale çıkmadı. Rybin konuşmayı ve inşayı paylaştı; ancak bunların hiçbiri, matematik topluluğunun varsayımı resmen kapatmasını sağlayacak hakem sürecinden geçmedi.

Yayımlanan tam grafik, bulabildiğim kadarıyla birincil bir kaynaktan bağımsız olarak yeniden inşa edilmedi. Dolaşan sayılar, onun paylaşımından ve paylaşılan transkriptden geliyor. Birkaç araştırmacı aritmetiğini kontrol edip tutarlı buldu ve biri, örneğinin aynı düğümler üzerinde sonsuz üç parametreli bir ailenin içinde yer aldığını gösterdi; bu da sonucu, tek seferlik bir şanstan daha zengin kılar. Teşvik edici, ama bu bir hakem raporu değil; gayriresmî topluluk kontrolü. 58’e karşı 60’ı yerleşik bir gerçek değil, iyi desteklenmiş bir iddia olarak değerlendirin.

1999 tarihli tıkanıklık teoremi bunların hiçbirinden etkilenmiyor.

Bir Desenin Parçası

Bu hikâye tekil bir veri noktası değil. Yaklaşık üç ay içinde AI desteğiyle düştüğü bildirilen üçüncü varsayım ve bu desen üzerinde durmaya değer.

20 Temmuz’da Claude Fable 5’in, matematikçi Levent Alpöğe’ye Jakoben varsayımına bir karşı-örnek bulmasında yardımcı olduğu bildirildi; 87 yıllık bir problem. Ondan önce, Mayıs’ta bir OpenAI modelinin 80 yıllık Erdős birim-mesafe varsayımını çürüttüğü söylendi. Bu haberle aynı hafta, Columbia’lı bir doktora öğrencisi, yapılandırılmış bir Codex iş akışıyla GPT-5.6’yı kullanarak beş günde altı açık Erdős problemini çözdü. Bir araştırmacının ifade ettiği gibi, ortak tema bu sistemlerin çürütmede ispatlamaktan daha iyi olduğudur. Bir karşı-örnek, kontrol edebileceğiniz tek bir tanıktır; bir ispat ise her olguyu kapsamak zorundadır. Bu asimetri, ilk düşen problemlerin hangileri olduğunu belirliyor gibi görünüyor.

Pratik çıkarım “AI matematiği çözer” değildir. Gördüğümüz, AI’nın sabırlı, kombinatorik olarak kapsamlı bir arama ortağı olarak çalışmasıdır: parametre ailelerini sayabilen, başarısızlık biçimlerini denemeler boyunca çalışma belleğinde tutabilen ve bir inşa kapanmadığında doğruyu söyleyebilen bir ortak. Bu, belirli ve faydalı bir yetenek. Ve bir sonraki hamlesinin nerede olacağını anlamak istiyorsanız, sorulacak soru hangi varsayımların daha eski olduğu değil, hangilerinin tek bir doğrulanabilir tanıkla bozulabileceğidir.