GPT-5.6 dan Dugaan Dinitz-Garg-Goemans

Pada 22 Juli 2026, Dmitry Rybin memposting sebuah klaim di X yang membuat sebagian orang meletakkan kopinya: GPT-5.6 Pro menghasilkan kontra­contoh untuk dugaan Dinitz-Garg-Goemans, masalah yang terbuka di optimisasi kombinatorial selama sekitar 30 tahun. Bukti konsepnya adalah sebuah graf kecil. Biaya aliran fraksional 58, biaya aliran tak-terbelah 60. Dua angka, tiga dekade, empat prompt.

Sebagian besar liputan mengulang angka-angka itu tanpa menunjukkan mekanisme di baliknya, padahal di mekanisme itulah pelajaran sesungguhnya berada. Di situlah saya juga harus jujur soal apa yang sudah diverifikasi dan apa yang belum. Versi singkat: konsepnya kokoh, beritanya adalah sebuah klaim dan belum menjadi teorema, dan jika Anda duduk mencoba membangun ulang graf yang persis sama dari nol, Anda akan paham kenapa masalah seperti ini sulit begitu rekonstruksi Anda mulai "bocor".

Jawaban Singkat

Rybin melaporkan bahwa GPT-5.6 Pro, diarahkan oleh empat prompt dengan total kurang dari 60 kata, menghasilkan klaim kontra­contoh untuk dugaan biaya Goemans, masalah yang terbuka sejak kira-kira 1999. Contohnya adalah graf terarah kecil dengan satu sumber dan tiga terminal pengantaran. Ia menyatakan perutean yang dapat dipecah (fraksional) berbiaya 58, sementara perutean tak-terbelah mana pun yang menjaga kemacetan dalam anggaran yang diizinkan berbiaya setidaknya 60. Selisih dua poin itu, jika lolos tinjauan formal, cukup untuk menjatuhkan dugaan tersebut.

Belum melalui telaah sejawat. Rybin menerbitkan percakapan lengkap ChatGPT sehingga siapa pun bisa membaca konstruksinya, dan beberapa orang telah memeriksa aritmetikanya dan menilainya konsisten. Aritmetika yang dapat direproduksi dan sebuah bukti yang diterima adalah dua hal berbeda, dan jarak di antara keduanya adalah keseluruhan kisah artikel ini.

Apa Itu Dugaan Dinitz-Garg-Goemans?

Sebelum kita bisa menghargai apa yang tumbang—atau mungkin—kita perlu memahami apa sebenarnya isi dugaannya.

Bayangkan sebuah gudang mengirim pesanan ke tiga kota melalui jaringan jalan. Jika Anda boleh membelah kiriman, Anda bisa mengirim separuh pesanan lewat satu jalan dan separuhnya lagi lewat jalan lain. Itulah perutean fraksional, dan itu fleksibel; biasanya menemukan himpunan jalur yang lebih murah. Namun banyak muatan nyata tidak bisa dibelah. Satu pesanan, satu truk, satu jalan, dari awal sampai akhir. Itulah aliran tak-terbelah, dan itulah yang harus dilakukan oleh pesanan angkutan, paket jaringan, atau kontainer pengiriman.

Pertanyaan yang dipikirkan orang sejak 1999 mudah diutarakan. Jika ada perutean fraksional yang murah, apakah Anda selalu dapat menemukan perutean tak-terbelah yang juga murah tanpa terlalu membebani jalan?

Yefim Dinitz, Naveen Garg, dan Michel Goemans menuntaskan setengahnya. Setengah lainnya adalah bagian yang disasar GPT-5.6. Untuk memahami betapa pentingnya pembedaan itu, kita perlu menelitinya secara tepat.

Teorema vs. Dugaan

Inilah pembedaan yang paling sering dikaburkan oleh banyak tulisan, jadi saya akan jelaskan dengan tepat sekali lalu mengandalkannya untuk sisa artikel.

Dinitz, Garg, dan Goemans membuktikan sebuah hasil tentang kemacetan: diberi aliran fraksional yang valid, Anda selalu bisa mengubahnya menjadi aliran tak-terbelah tanpa melampaui kapasitas jalan mana pun lebih dari permintaan terbesar tunggal, sebut saja nilainya D. Teorema itu tidak dipertanyakan dan memang tidak pernah.

Yang secara terpisah diduga oleh Goemans adalah versi yang lebih kuat dan mempertimbangkan biaya: bahwa konversi yang sama dapat sekaligus menahan total biaya tetap rendah ketika menahan kemacetan tetap rendah. Kemacetan dan biaya, keduanya dibatasi, dalam satu perutean. Teorema kemacetan saja aman. Dugaan biaya-plus-kemacetan adalah bagian yang Rybin klaim telah tumbang. Jika ada satu kalimat yang Anda bawa pulang dari tulisan ini, jadikan itu. Banyak liputan yang heboh diam-diam menukar keduanya, dan perbedaan di antara keduanya adalah celah matematis yang butuh 30 tahun untuk ditutup.

Apa yang Sebenarnya Dibangun GPT-5.6

Contoh Rybin cukup kecil untuk dijelaskan dalam satu paragraf. Sebuah sumber, beberapa simpul perantara membentuk "tulang punggung" bersama, dan tiga terminal, masing-masing membawa permintaan. Setiap terminal punya dua jalan pulang: jalur langsung yang mahal, atau jalan memutar gratis melalui tulang punggung bersama.

Ketegangannya bersifat struktural. Jalan memutar murah berebut ruang di tulang punggung, sehingga jika terlalu banyak terminal mencoba rute murah sekaligus, salah satu jalan di tulang punggung meluap. Dorong cukup jauh dan hanya satu terminal yang bisa mengambil jalur murahnya dalam perutean tak-terbelah yang valid. Sisanya terdorong ke jalur langsung yang mahal, dan biaya naik. Aliran fraksional, yang bebas membelah, menyebarkan tiap permintaan di kedua jalur dan menyelinap di bawah setiap kapasitas sekaligus. Begitulah Anda mendapatkan biaya fraksional lebih rendah dari biaya tak-terbelah legal termurah. Angka Rybin untuk contohnya adalah 58 dan 60.

Saya akan jujur soal satu batasan di sini. Saya belum berhasil mereproduksi graf Rybin yang persis, kapasitas spesifik dan konflik berpasangan, dari sumber primer. Transkripnya menggambarkan satu titik tertentu dalam sebuah keluarga parameter, dan deskripsi "tujuh simpul" yang banyak dibagikan adalah abstraksinya, bukan konstruksi yang sudah saya verifikasi per sisi. Jadi saya tidak akan mementaskan derivasi rapi angka 58 dan berpura-pura itu miliknya. Yang bisa saya lakukan adalah memberikan Anda sebuah contoh mandiri yang menunjukkan mekanisme yang sama, cukup kecil untuk diperiksa secara brute force, agar Anda bisa melihat sendiri seperti apa "fraksional mengalahkan setiap tak-terbelah legal". 

Empat Prompt, Beberapa Jam

Jumlah prompt adalah bagian yang paling tidak menarik dari kisah ini, meskipun itu yang viral.

Log percakapan yang dibagikan Rybin memperlihatkan modelnya gagal terlebih dulu, dan gagal dengan akurat. Prompt pembuka memintanya mencari kontra­contoh terstruktur. Ia bekerja hampir satu jam dan kembali tanpa hasil, menyatakan terus terang bahwa menyajikan apa yang ia punya sebagai kontra­contoh valid akan keliru.

Diminta untuk lanjut, ia berjalan lagi, dan lagi-lagi melaporkan nihil, menjelaskan bagaimana tiap konstruksi yang menjanjikan selalu memunculkan opsi rute tambahan tersembunyi yang menghancurkan pemisahan biaya-kemacetan begitu semua jalur dienumerasi. Prompt ketiga yang meminta strategi lebih bersih menghasilkan kerangka yang lebih sempit namun tetap tanpa hasil akhir.

Itu bukan "empat prompt, selesai." Itu berjam-jam sebuah model menabrak tembok dan berkata jujur tentangnya. Tembok spesifik yang terus ditemuinya—muncul rute ekstra dan merusak pemisahan—adalah tepat yang akhirnya dihindari oleh konstruksi final, dengan mengikat setiap terminal pada tepat dua jalur sehingga seluruh ruang perutean adalah delapan opsi yang bisa Anda enumerasi dengan tangan. Ingat modus kegagalan itu. Anda akan mengalaminya sendiri sebentar lagi.

Prompt keempat, yang kabarnya mendekati "sudah cukup dengan kegagalanmu, tolong selesaikan dengan kontra­contoh lengkap tanpa syarat," adalah yang menghasilkan konstruksi bekerja, beserta sertifikat bukti, program enumerasi, dan LaTeX lengkap. Kesabaran itu penting. Begitu juga penolakan-penolakan sebelumnya; itu penilaian diri yang jujur.

Periksa Sendiri

Di sinilah liputan DataCamp bisa melakukan sesuatu yang tidak bisa dilakukan oleh berita: memungkinkan Anda menjalankan verifikasi.

Satu penjelasan cepat sebelum kodenya. Yang berikut ini bukan graf Rybin. Ini adalah contoh skematik yang saya buat agar jujur, di mana setiap terminal benar-benar hanya memiliki tepat dua rute, aritmetikanya menutup, dan selisihnya nyata. Ini menunjukkan bentuk sebuah kontra­contoh semacam itu dan teknik untuk memeriksanya. Ini sendiri tidak membantah apa pun, dan saya akan jelaskan alasannya setelah Anda menjalankannya.

Pengaturan: tiga terminal, masing-masing mengirim 10 unit, jadi permintaan terbesar D adalah 10. Masing-masing punya jalur langsung yang mahal (biaya 30) dan jalur murah gratis. Jalur murah diatur sehingga setiap pasangan di antaranya bertarung atas jalan hambatan privatnya sendiri, jalan A dipakai terminal 1 dan 2, jalan B oleh terminal 1 dan 3, jalan C oleh terminal 2 dan 3. Dalam aliran fraksional, tiap terminal mengirim 2/5 permintaannya lewat jalur murah dan 3/5 mahal, yang berbiaya 30 x 3/5 x 3 = 54. Setiap jalan kemudian membawa 4 + 4 = 8 unit secara fraksional, dan anggaran kemacetan adalah muatan itu ditambah D, jadi 18.

Sekarang lihat apa yang dilakukan perutean tak-terbelah terhadap itu. Dua terminal sama-sama memilih murah menumpahkan 10 + 10 = 20 unit ke jalan bersama mereka, melampaui anggaran 18. Jadi paling banyak satu terminal yang bisa merute murah; dua lainnya membayar 30 masing-masing. Biaya tak-terbelah legal minimum: 60. Melawan fraksional 54. Ada delapan perutean, jadi kita cek semuanya:

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

Jalankan dan Anda akan mendapatkan biaya fraksional 54, biaya tak-terbelah legal minimum 60, dan selisih 6. Tiga baris yang kelebihan muatan adalah tiga konflik berpasangan; satu-satunya perutean yang lolos menjaga paling banyak satu terminal yang murah.

Jadi dugaannya gugur? Tidak juga, dan inilah bagian yang saya janji akan jelaskan. Enumerasi delapan baris itu hanya berkata benar jika setiap terminal benar-benar punya dua rute dan tidak lebih. Bangun graf ini dari jalan dan simpul nyata, dan rute murah keempat cenderung muncul dari kombinatorikanya. Sebuah terminal menemukan jalan pulang ketiga yang murah dan tetap di bawah anggaran, dan selisihnya hilang. Rute ekstra itu adalah kegagalan persis yang dilaporkan model pada tiga percobaan pertamanya. Sebuah gawai yang bersih dan simetris yang mematahkan dugaan 30 tahun dalam delapan baris Python akan terlalu indah untuk jadi kenyataan—dan memang begitu. Kode di atas membuktikan bahwa pemeriksaannya sehat dan sifat targetnya nyata. Apakah suatu graf tertentu benar-benar memiliki sifat itu, tanpa kebocoran, adalah bagian tersulit, dan itulah mengapa contoh asli Rybin adalah titik teratur dalam keluarga parameter, bukan segitiga rapi.

Apa yang Masih Belum Tuntas

Belum ada makalah formal yang muncul. Rybin membagikan percakapan dan konstruksinya; keduanya belum melalui proses referen yang memungkinkan komunitas matematika secara resmi menutup dugaan tersebut.

Graf yang persis dipublikasikan belum dibangun ulang secara independen dari sumber primer yang bisa saya temukan. Angka-angka yang beredar berasal dari postingannya dan transkrip yang dibagikan. Beberapa peneliti telah memeriksa aritmetikanya dan menyebutnya konsisten, dan satu orang menunjukkan contohnya berada dalam keluarga tiga-parameter tak hingga pada simpul yang sama, yang akan membuat hasilnya lebih kaya daripada sekadar kebetulan. Menggembirakan, tetapi itu pemeriksaan komunitas informal, bukan laporan referen. Perlakukan 58 vs 60 sebagai klaim yang didukung baik, bukan fakta yang sudah final.

Teorema kemacetan tahun 1999 tidak tersentuh oleh semua ini.

Bagian dari Pola

Kisah ini bukan satu titik data. Ini adalah dugaan ketiga yang dilaporkan tumbang oleh bantuan AI dalam sekitar tiga bulan, dan polanya patut dicermati.

Pada 20 Juli, Claude Fable 5 kabarnya membantu matematikawan Levent Alpöge menemukan kontra­contoh untuk dugaan Jacobian, masalah berusia 87 tahun. Sebelumnya, pada Mei, sebuah model OpenAI disebut telah membantah dugaan jarak-satu unit Erdős yang berusia 80 tahun. Minggu yang sama dengan kabar ini, seorang mahasiswa PhD Columbia menggunakan GPT-5.6 dengan alur kerja Codex terstruktur untuk menyelesaikan enam masalah terbuka Erdős dalam lima hari. Benang merahnya, seperti dikatakan seorang peneliti, adalah bahwa sistem-sistem ini lebih baik dalam membantah daripada membuktikan. Sebuah kontra­contoh adalah satu saksi yang bisa Anda cek; sebuah bukti harus mencakup setiap kasus. Asimetri itu tampaknya menentukan masalah mana yang tumbang lebih dulu.

Inti praktisnya bukan "AI memecahkan matematika." Yang kita saksikan adalah AI bekerja sebagai mitra pencarian yang sabar dan secara kombinatorial menyeluruh: yang dapat mengenumerasi keluarga parameter, menyimpan modus kegagalan dalam memori kerja lintas percobaan, dan berkata jujur ketika sebuah konstruksi tidak menutup. Itu kemampuan yang spesifik dan berguna. Dan jika Anda ingin memahami di mana kemungkinan akan menyerang berikutnya, pertanyaan yang perlu diajukan bukan mana dugaan yang paling tua, melainkan mana yang bisa dipatahkan oleh satu saksi yang dapat diperiksa.