GPT-5.6 dan Konjektur Dinitz-Garg-Goemans

Pada 22 Juli 2026, Dmitry Rybin mengunggah sebuah klaim di X yang membuat sebagian orang menaruh cangkir kopi mereka: GPT-5.6 Pro telah menghasilkan contoh tandingan untuk konjektur Dinitz-Garg-Goemans, masalah yang terbuka di optimisasi kombinatorial selama sekitar 30 tahun. Bukti konsepnya adalah satu graf kecil. Biaya aliran fraksional 58, biaya aliran tak-terbelah 60. Dua angka, tiga dekade, empat prompt.

Sebagian besar liputan mengulang angkanya tanpa menunjukkan mekanisme di baliknya, padahal justru di mekanismelah pelajaran sebenarnya berada. Di situlah saya juga harus terus terang kepada Anda tentang apa yang sudah diverifikasi dan apa yang belum. Versi singkatnya: konsepnya kokoh, beritanya adalah sebuah klaim dan belum menjadi teorema, dan jika Anda duduk untuk mereproduksi graf yang persis sama dari nol, Anda akan paham mengapa masalah seperti ini sulit tepat saat rekonstruksi Anda mulai bocor.

Jawaban Singkat

Rybin melaporkan bahwa GPT-5.6 Pro, diarahkan dengan empat prompt total kurang dari 60 kata, menghasilkan klaim contoh tandingan untuk konjektur biaya Goemans, sebuah masalah yang terbuka sejak sekitar 1999. Kasusnya adalah graf berarah kecil dengan satu sumber dan tiga terminal pengantaran. Ia menyatakan perutean yang dapat dipecah (fraksional) berbiaya 58, sementara setiap perutean tak-terbelah yang menjaga kemacetan dalam batas anggaran yang diizinkan berbiaya setidaknya 60. Selisih dua poin itu, jika lolos tinjauan formal, cukup untuk menggugurkan konjektur tersebut.

Ini belum melalui ulasan sejawat. Rybin memublikasikan percakapan ChatGPT lengkap agar siapa pun bisa membaca konstruksinya, dan beberapa orang telah memeriksa aritmetikanya dan menyatakan konsisten. Aritmetika yang dapat direproduksi dan sebuah bukti yang diterima adalah dua hal yang berbeda, dan jarak di antara keduanya adalah keseluruhan cerita artikel ini.

Apa Itu Konjektur Dinitz-Garg-Goemans?

Sebelum kita dapat menghargai apa yang runtuh—atau mungkin—kita perlu memahami apa sebenarnya yang dikatakan konjektur tersebut.

Bayangkan sebuah gudang mengirim pesanan ke tiga kota melalui jaringan jalan. Jika Anda boleh membagi kiriman, Anda bisa mengirim setengah pesanan di satu jalan dan setengahnya lagi di jalan lain. Itulah perutean fraksional, dan fleksibel; biasanya menemukan himpunan jalur yang lebih murah. Namun banyak muatan nyata tidak bisa dibagi. Satu pesanan, satu truk, satu jalan, dari awal hingga akhir. Itulah aliran tak-terbelah, dan itulah yang harus dilakukan oleh pesanan kargo, paket jaringan, atau kontainer pengiriman.

Pertanyaan yang digeluti orang sejak 1999 mudah diucapkan. Jika ada perutean fraksional yang murah, dapatkah Anda selalu menemukan perutean tak-terbelah yang juga murah tanpa terlalu membebani jalan?

Yefim Dinitz, Naveen Garg, dan Michel Goemans menyelesaikan separuhnya. Separuh lain adalah bagian yang disasar GPT-5.6. Untuk memahami mengapa pembedaan itu sangat penting, kita perlu presisi tentang hal tersebut.

Teorema vs. Konjektur

Ini adalah pembedaan yang paling sering dikaburkan oleh banyak ulasan, jadi saya akan presisi sekali lalu mengandalkannya untuk sisa artikel.

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

Yang secara terpisah dikemukakan sebagai konjektur oleh Goemans adalah versi yang lebih kuat dan sadar-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. Konjektur biaya-plus-kemacetan adalah bagian yang dikatakan Rybin runtuh. Jika Anda hanya mengambil satu kalimat dari tulisan ini, jadikan itu. Banyak liputan yang bersemangat secara halus menukar keduanya, dan perbedaan di antara keduanya adalah seluruh kesenjangan matematis yang memakan waktu 30 tahun untuk ditutup.

Apa yang Sebenarnya Dibangun GPT-5.6

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

Ketegangannya bersifat struktural. Jalan memutar murah saling berebut ruang di tulang punggung, jadi jika terlalu banyak terminal mencoba merute murah sekaligus, sebuah jalan di tulang punggung meluap. Dorong cukup jauh dan hanya satu terminal yang dapat mengambil jalur murahnya dalam perutean tak-terbelah yang valid. Sisanya terpaksa melalui jalur langsung yang mahal, dan biayanya naik. Aliran fraksional, yang bebas membagi, menyebarkan setiap permintaan di kedua jalur dan lolos di bawah setiap kapasitas sekaligus. Begitulah Anda mendapatkan biaya fraksional di bawah biaya tak-terbelah legal termurah. Angka Rybin untuk kasusnya adalah 58 dan 60.

Saya akan jujur tentang satu batasan. Saya belum berhasil mereproduksi graf persis milik Rybin, 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 telah saya verifikasi sisi-dem sisi. Jadi saya tidak akan menyajikan derivasi rapi angka 58 dan berpura-pura itu miliknya. Yang bisa saya lakukan adalah memberikan Anda sebuah kasus mandiri yang menunjukkan mekanisme yang sama, cukup kecil untuk diperiksa secara brute force, sehingga Anda bisa melihat sendiri seperti apa "fraksional mengalahkan setiap tak-terbelah yang legal". 

Empat Prompt, Beberapa Jam

Jumlah prompt adalah bagian paling tidak menarik dari cerita ini, meski itulah yang viral.

Log chat yang dibagikan Rybin menunjukkan model pertama kali gagal, dan gagal secara akurat. Prompt pembuka memintanya menemukan contoh tandingan terstruktur. Ia bekerja selama hampir satu jam dan kembali dengan tangan kosong, menyatakan terus terang bahwa menyajikan apa yang dimilikinya sebagai contoh tandingan yang valid akan salah.

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

Itu bukan "empat prompt, selesai." Itu berjam-jam sebuah model menabrak tembok dan jujur mengatakannya. Tembok spesifik yang terus ditabraknya—munculnya jalur ekstra yang merusak pemisahan—adalah persis apa yang dibangun oleh konstruksi final untuk dicegah, dengan memasang setiap terminal pada tepat dua jalur sehingga seluruh ruang perutean adalah delapan opsi yang bisa Anda enumerasi secara manual. Ingatlah mode kegagalan itu. Anda akan segera mengalaminya sendiri.

Prompt keempat, yang kabarnya mirip dengan "sudah cukup dengan kegagalanmu, tolong selesaikan dengan contoh tandingan lengkap dan tanpa syarat," adalah yang menghasilkan konstruksi yang bekerja, beserta sertifikat bukti, program enumerasi, dan LaTeX lengkap. Kesabaran itu penting. Demikian pula penolakan sebelumnya; itu adalah penilaian diri yang jujur.

Periksa Sendiri

Inilah bagian di mana liputan DataCamp bisa melakukan sesuatu yang tak bisa dilakukan berita: membiarkan Anda menjalankan verifikasinya.

Catatan cepat sebelum kode. Yang berikut ini bukan graf milik Rybin. Ini adalah kasus 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 dari contoh tandingan semacam itu dan teknik untuk memeriksanya. Ini tidak, sendirinya, membantah apa pun, dan saya akan jelaskan alasannya tepat setelah Anda menjalankannya.

Pengaturan: tiga terminal, masing-masing mengirim 10 unit, jadi permintaan terbesar D adalah 10. Masing-masing memiliki jalur langsung mahal (biaya 30) dan jalur murah gratis. Jalur murah diatur sehingga setiap pasangan di antaranya berebut jalan leher-botol privatnya sendiri, jalan A dibagi terminal 1 dan 2, jalan B oleh terminal 1 dan 3, jalan C oleh terminal 2 dan 3. Dalam aliran fraksional, setiap terminal mengirim 2/5 permintaannya melalui jalur murah dan 3/5 melalui jalur mahal, yang biayanya 30 x 3/5 x 3 = 54. Setiap jalan kemudian membawa 4 + 4 = 8 unit secara fraksional, dan anggaran kemacetan adalah beban itu plus D, jadi 18.

Sekarang lihat apa yang dilakukan perutean tak-terbelah terhadap itu. Dua terminal yang sama-sama mengambil jalur murah menaruh 10 + 10 = 20 unit pada jalan bersama mereka, melebihi 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 periksa 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 beban adalah tiga konflik berpasangan; satu-satunya perutean yang lolos menjaga paling banyak satu terminal yang murah.

Jadi konjekturnya mati? Tidak juga, dan ini bagian yang saya janjikan untuk dijelaskan. Enumerasi delapan baris itu hanya berkata jujur jika setiap terminal benar-benar memiliki 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 dalam anggaran, dan selisihnya tertutup. Rute ekstra itulah kegagalan yang dilaporkan model pada tiga percobaan pertamanya. Sebuah gawai yang bersih dan simetris yang mematahkan konjektur 30 tahun dalam delapan baris Python akan terlalu indah untuk jadi kenyataan—dan memang begitu. Kode di atas membuktikan bahwa pemeriksaannya valid dan properti sasarannya nyata. Apakah sebuah graf tertentu benar-benar memiliki properti itu, tanpa kebocoran, adalah bagian sulitnya, dan itulah mengapa kasus nyata Rybin adalah titik yang disetel dalam sebuah keluarga parameter alih-alih segitiga rapi.

Apa yang Masih Belum Tuntas

Belum ada makalah formal yang muncul. Rybin membagikan percakapan dan konstruksinya; tidak satupun yang melalui proses wasit yang memungkinkan komunitas matematika secara resmi menutup konjektur tersebut.

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

Teorema kemacetan tahun 1999 tidak tersentuh oleh semua ini.

Bagian dari Pola

Kisah ini bukan satu titik data. Ini adalah konjektur ketiga yang dilaporkan runtuh karena bantuan AI dalam sekitar tiga bulan, dan polanya layak direnungkan.

Pada 20 Juli, Claude Fable 5 kabarnya membantu matematikawan Levent Alpöge menemukan contoh tandingan untuk konjektur Jacobian, sebuah masalah berusia 87 tahun. Sebelumnya, pada Mei, sebuah model OpenAI disebut-sebut telah mematahkan konjektur jarak-satuan 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. Contoh tandingan adalah satu saksi yang dapat Anda periksa; sebuah bukti harus mencakup setiap kasus. Asimetri itu tampaknya menentukan masalah mana yang lebih dulu jatuh.

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