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

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

Çoğu haber, sayıların arkasındaki mekanizmayı göstermeden rakamları tekrar ediyor; oysa dersin asıl yeri mekanizma. Ayrıca burada, nelerin doğrulandığı ve nelerin henüz doğrulanmadığı konusunda açık olmam gerekiyor. Kısa sürüm: kavramlar sağlam, haber bir iddia ve henüz teorem değil; sıfırdan tam aynı grafiği yeniden kurmaya oturduğunuzda, yeniden inşanız ilk sızdırmaya başladığı anda bu tür problemlerin neden zor olduğunu deneyimleyerek öğreniyorsunuz.

Hızlı Yanıt

Rybin, toplamda 60 kelimenin altında dört istemle yönlendirilen GPT-5.6 Pro’nun, yaklaşık 1999’dan beri açık olan Goemans’ın maliyet varsayımına karşı bir örnek ürettiğini bildiriyor. Örneği, tek bir kaynak ve üç teslim terminali olan küçük bir yönlendirilmiş graf. Bölünebilir (kesirli) yönlendirmenin maliyetinin 58, izin verilen sıkışıklık bütçesini aşmadan yapılan her bölünemez yönlendirmenin maliyetinin ise en az 60 olduğunu belirtiyor. Bu iki puanlık fark, resmi incelemeyi geçerse, varsayımı çürütmeye yeter.

Henüz hakemli incelemeden geçmedi. Rybin, herkesin inşayı okuyabilmesi için tam ChatGPT konuşmasını yayımladı ve birkaç kişi hesabını kontrol edip tutarlı buldu. Yeniden üretilebilir bir aritmetik ile kabul görmüş bir ispat ise farklı şeyler ve aralarındaki mesafe bu yazının tüm hikâyesi.

Dinitz-Garg-Goemans Varsayımı Nedir?

Ne düştü, ya da düşmüş olabilir, anlayabilmek için varsayımın ne söylediğini bilmemiz gerekiyor.

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, yarısını başka bir yoldan gönderebilirsiniz. Bu kesirli yönlendirmedir ve esnektir; genellikle daha ucuz bir yol kümesi bulur. Ama 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 siparişinin, bir ağ paketinin veya 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 aşırı 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üler. Diğer yarı ise GPT-5.6’nın hedef aldığı kısım. Bu ayrımın neden son derece önemli olduğunu anlamak için nokta atışı yapmamız gerekiyor.

Teorem ile Varsayım

Birçok yazının bulanıklaştırdığı ayrım bu; o yüzden burada bir kez netleştirip yazının geri kalanında ona dayanacağım.

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

Goemans’ın ayrıca öne sürdüğü ise daha güçlü, maliyet odaklı versiyondu: Aynı dönüşümün, sıkışıklığı sınırlarken toplam maliyeti de aşağıda tutabileceği. Tek bir yönlendirmede hem sıkışıklık hem maliyet, her ikisi de sınırlı. Yalnızca sıkışıklık teoremi güvende. Maliyet artı sıkışıklık varsayımı ise Rybin’in çöktüğünü söylediği parça. Bu yazıdan tek bir cümle aklınızda kalacaksa bu olsun. Heyecanlı haberler ikisini sessizce birbirine karıştırıyor ve aralarındaki fark, kapanması 30 yıl alan matematiksel boşluğun ta kendisi.

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

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

Gerginlik yapısal. Ucuz dolambaçlar omurga üzerinde yer için rekabet ediyor; dolayısıyla çok fazla terminal aynı anda ucuza yönlenmeye çalışırsa, bir omurga yolu taşıp taşıyor. Bunu yeterince zorlarsanız, geçerli herhangi bir bölünemez yönlendirmede en fazla bir terminal ucuz yolunu alabiliyor. Kalanlar pahalı doğrudan yollarına zorlanıyor ve maliyet artıyor. Kesirli akış ise, bölünebildiği için, her talebi her iki yol arasında yayıp tüm kapasitelerin altından aynı anda sızıyor. Böylece kesirli maliyeti, en ucuz yasal bölünemez maliyetin altına indiriyorsunuz. Rybin’in örneğinde rakamlar 58 ve 60.

Burada bir sınıra dürüstçe değineceğim. Rybin’in tam grafiğini, belirli kapasiteleri ve ikili çatışmaları birincil kaynaktan yeniden üretemedim. Transkripti, bir parametre ailesinde belirli bir noktayı tarif ediyor ve yaygın şekilde paylaşılan “yedi düğüm” anlatımı bunun soyutlaması; kenar kenar doğruladığım bir inşa değil. Bu yüzden 58’i pürüzsüzce türetip sanki onunkiymiş gibi sunmayacağım. Yapabileceğim şey, aynı mekanizmayı gösteren, kaba kuvvetle kontrol edilebilecek kadar küçük, kendi içinde tutarlı bir örnek sunmak; böylece “kesirli, tüm yasal bölünemezleri yener” ifadesinin neye benzediğini kendi gözlerinizle görebilirsiniz. 

Dört İstem, Birkaç Saat

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

Rybin’in paylaştığı sohbet günlüğü, modelin önce başarısız olduğunu ve dürüstçe başarısız olduğunu gösteriyor. Açılış istemi, modeli yapısal bir karşı-örnek bulmaya davet etti. Model yaklaşık bir saat çalıştı ve eli boş döndü; elindeki şeyi geçerli bir karşı-örnek olarak sunmanın yanlış olacağını açıkça belirtti.

Devam etmesi söylenince yeniden çalıştı ve yine bir şey bulamadığını bildirdi; her umut verici inşanın tüm yollar sayıldığında gizli bir ekstra yönlendirme seçeneği belirdiğini, bunun da maliyet-sıkışıklık ayrımını yok ettiğini anlattı. Daha temiz bir strateji isteyen üçüncü istem, daha dar bir çerçeve sağladı ama yine bitmiş bir sonuç getirmedi.

Bu “dört istem, bitti” değil. Bu, bir modelin saatlerce duvara toslayıp bunun hakkında doğruyu söylemesi. Sürekli çarptığı belirli duvar, fazladan bir rota belirip ayrımı bozması, nihai inşanın tam da bunu önlemek için tasarlandığı şeydi: her terminali tam iki yola sabitleyerek tüm yönlendirme uzayını elle sayabileceğiniz sekiz seçeneğe indirgemek. Bu başarısızlık türünü aklınızda tutun. Az sonra siz de onunla karşılaşacaksınız.

Dördüncü istemin, bildirildiğine göre, “yeter artık bu başarısızlığın, lütfen eksiksiz ve koşulsuz bir karşı-örnekle bitir”e yakın bir şey olduğu, çalışan inşayı ürettiği; bununla birlikte ispat sertifikaları, bir sayım programı ve tam LaTeX çıktısı verdiği belirtiliyor. Sabır önemliydi. Önceki retler de öyleydi; dürüst öz değerlendirmelerdi.

Kendiniz Kontrol Edin

İşte DataCamp içeriğinin bir haber yazısının yapamayacağını yapabileceği yer: doğrulamayı çalıştırabilirsiniz.

Koda geçmeden hızlı bir uyarı. Aşağıdaki, Rybin’in grafı değildir. Bu, her terminalin gerçekten tam iki rotası olduğu, aritmetiğin kapandığı ve farkın gerçek olduğu dürüst bir şematik örnek. Böyle bir karşı-örneğin şeklini ve kontrol tekniğini gösteriyor. Tek başına hiçbir şeyi çürütmez; nedenini de siz çalıştırdıktan hemen sonra açıklayacağım.

Kurulum: üç terminal, her biri 10 birim gönderiyor; dolayısıyla en büyük talep D = 10. Her birinin pahalı bir doğrudan yolu (maliyet 30) ve ücretsiz bir ucuz yolu var. Ucuz yollar, her ikilinin kendi özel dar boğaz yolunda çakışacak şekilde düzenlenmiş: A yolu 1 ve 2 terminalleri tarafından, 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 tutuyor. Her yol kesirli olarak 4 + 4 = 8 birim taşıyor ve sıkışıklık bütçesi bu yük artı D, yani 18.

Şimdi bölünemez yönlendirme buna ne yapıyor, izleyin. İki terminalin ucuza gitmesi, paylaştıkları yola 10 + 10 = 20 birim yüklüyor; 18’lik bütçeyi aşıyor. Dolayısıyla en fazla bir terminal ucuza yönlenebilir; diğer ikisi 30’ar öder. Asgari yasal bölünemez maliyet: 60. Kesirli maliyete karşı 54. Sekiz yönlendirme mümkün, dolayısıyla hepsini kontrol ediyoruz:

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 ediyorsunuz. Aşırı yüklü üç satır, üç ikili çatışma; ayakta kalan tek yönlendirmeler en fazla bir terminali ucuza bırakıyor.

Öyleyse varsayım öldü mü? Tam değil; söz verdiğim kısım burası. Bu sekiz satırlık sayım, her terminalin gerçekten iki rotası ve fazlası olmadığı durumda doğruyu söyler. Bu grafiği gerçek yollar ve düğümlerle kurduğunuzda, kombinatoriklerden dördüncü bir ucuz rota belirme eğilimindedir. Bir terminal, ucuz olan ve bütçeyi aşmayan üçüncü bir dönüş yolu bulur ve fark kapanır. Bu fazladan rota, modelin ilk üç denemesinde rapor ettiği tam hatadır. Sekiz satır Python’la 30 yıllık bir varsayımı bozan temiz, simetrik bir düzenek gerçek olamayacak kadar iyi olurdu ve öyle. Yukarıdaki kod, kontrolün sağlam olduğunu ve hedef özelliğin gerçek olduğunu kanıtlıyor. Belirli bir grafın bu özelliğe gerçekten sahip olup olmaması, sızıntısız biçimde, zor olan kısım; ve Rybin’in gerçek örneğinin neden derli toplu bir üçgen yerine bir parametre ailesinde ayarlı bir nokta olduğunu açıklıyor.

Hâlâ Çözümsüz Olanlar

Resmî bir makale yayımlanmadı. Rybin konuşmayı ve inşayı paylaştı; ikisi de varsayımı resmen kapatacak hakem sürecinden geçmedi.

Yayımlanan tam graf, bulabildiğim birincil kaynaktan bağımsız olarak yeniden inşa edilmedi. Dolaşan sayılar, onun gönderisinden ve paylaşılan transkriptinden 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 tesadüften daha zengin kılar. Cesaret verici, ancak bu gayriresmî topluluk kontrolü; hakem raporu değil. 58’e karşı 60’ı, sağlam temellere dayanan bir iddia olarak, yerleşik bir gerçek değilmiş gibi ele alın.

1999 tarihli sıkışıklık teoremi bunların hiçbirinden etkilenmedi.

Bir Desenin Parçası

Bu hikâye tekil bir veri noktası değil. Yaklaşık üç ayda, yapay zekâ yardımıyla çöktüğü bildirilen üçüncü varsayım ve bu desen üzerinde durmaya değer.

20 Temmuz’da, Claude Fable 5’in matematikçi Levent Alpöge’ye Jacobian varsayımına karşı bir karşı-örnek bulmasında yardımcı olduğu bildirildi; 87 yıllık bir problem. Ondan önce, Mayıs ayında, bir OpenAI modelinin 80 yıllık Erdős birim-mesafe varsayımını çürüttüğü söylenmişti. 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, ana hat, bu sistemlerin ispatlamaktan ziyade çürütmede daha iyi oluşu. Bir karşı-örnek, kontrol edebileceğiniz tek bir tanıktır; bir ispat ise her durumu kapsamalıdır. Bu asimetri, önce hangi problemlerin düştüğünü belirliyor gibi görünüyor.

Pratik çıkarım “Yapay zekâ matematiği çözüyor” değil. Gözlemlediğimiz şey, sabırlı, kombinatorik olarak kapsamlı bir arama ortağı olarak çalışan yapay zekâ: parametre ailelerini sıralayabilen, başarısızlık türlerini 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 sırada nerede etkili olabileceğini anlamak istiyorsanız, sorulacak şey hangi varsayımların en eski olduğu değil, hangilerinin tek bir doğrulanabilir tanıkla kırılabileceği.