Lagi?? GPT-5.6 baru-baru ini sepertinya telah mengganggu sarang contoh matematis berlawanan...
Dinitz-Garg-Goemans conjecture, yang telah ada dalam teori graf selama hampir 30 tahun, baru saja ditemukan contoh penyangkalnya oleh GPT-5.6 Pro.
Seorang peneliti bernama Dmitry Rybin hanya memasukkan 4 prompt selama seluruh proses argumen, dengan total 58 kata bahasa Inggris.
Tanpa promp engineering ribuan kata, tanpa rumus rumit, sepanjang teks pada dasarnya seluruhnya:
Lanjutkan penelitian, lanjutkan mencari, beri saya satu contoh lengkap sebaliknya!!!
Dengan mendorong terus-menerus seperti ini, GPT-5.6 Pro benar-benar menghasilkan kesimpulan yang sangat luar biasa—
Konjektur Dinitz-Garg-Goemans salah.
Yang diserahkan oleh AI selain sketsa, juga terdiri dari empat halaman sertifikat bukti, program verifikasi ekshaustif presisi, data contoh penyangkal yang dapat dibaca mesin, dan kode sumber LaTeX.
Lalu, dugaan matematika yang bertahan selama hampir 30 tahun, tiba-tiba terungkap memiliki bug mematikan hanya karena beberapa 「tanda kematian」???
Dugaan selama 30 tahun, ditemukan Bug mematikan oleh GPT-5.6 Pro
Mari kita bahas terlebih dahulu, apa sebenarnya yang diteliti oleh dugaan Dinitz-Garg-Goemans yang namanya sangat panjang ini.
Kita bisa langsung membayangkannya sebagai masalah pengiriman.
Misalkan sebuah gudang harus mengirimkan barang ke beberapa tujuan, ketika pembagian diperbolehkan, barang dalam satu kiriman dapat dipisahkan dan dikirim melalui beberapa rute—
Setengah naik jalan tol, setengah lewat jalan nasional, selama semuanya sampai tujuan, itu sudah OK～
Namun, di bawah aturan non-divisible, setiap pengiriman harus menempuh satu rute secara utuh, tidak boleh dibagi!!!
Sebenarnya, situasi seperti ini cukup umum di dunia nyata, misalnya dalam data jaringan, pesanan logistik, pengaturan lalu lintas, dan alokasi rantai pasokan, semua menghadapi masalah serupa:
Solusi matematis optimal dapat membagi tugas menjadi tak hingga banyak bagian kecil, tetapi dalam kenyataannya, sebuah mobil atau pesanan tidak dapat dibagi menjadi 0,37 bagian.
△
Namun, setelah pembagian dilarang, solusi optimal sebelumnya juga sulit untuk langsung diterapkan.
Barang yang sebelumnya tersebar di beberapa rute sekarang harus dipadatkan ke dalam satu rute saja, sehingga beban pada sebagian rute kemungkinan besar akan meningkat secara mendadak.
Jadi, masalah yang sebenarnya perlu dipecahkan adalah:
Bagaimana cara mengubah solusi "dapat diangkut terpisah" menjadi "harus diangkut secara keseluruhan", tanpa menyebabkan kemacetan jalan yang terlalu parah?
Pada tahun 1999, Yefim Dinitz, Naveen Garg, dan Michel Goemans menerbitkan makalah klasik di bidang aliran tak terbagi sumber tunggal, dan membuktikan bahwa kemacetan semacam ini dapat dikendalikan dalam batas tertentu.
Tetapi setelah menyelesaikan masalah "akan terlalu macet atau tidak", masih ada masalah lain yang sangat nyata: apakah akan menjadi lebih mahal?
Dengan demikian, ahli terkenal di bidang optimasi kombinatorial, Goemans, kembali mengusulkan versi biaya yang lebih kuat—
Sambil mempertahankan batas atas overload di atas, total biaya juga seharusnya tidak melebihi skema distribusi sebelumnya.
Singkatnya, dulu dengan membagi pengiriman, kita bisa mendapatkan biaya murah dan tidak terlalu macet; sekarang, dengan persyaratan bahwa setiap kiriman harus melalui satu rute utuh, secara teori kita juga harus menemukan solusi yang sama murahnya, dan paling banyak hanya menambah kemacetan untuk satu kiriman.
Namun, dugaan yang tampaknya cukup intuitif ini belum pernah dibuktikan pada struktur graf umum, dan penelitian selanjutnya hanya berhasil menyelesaikan sebagian kasus khusus.
Selama bertahun-tahun setelah itu, dugaan ini tidak terbukti maupun dibantah.
Namun, contoh sebaliknya yang diberikan oleh GPT-5.6 Pro justru menghambat dua hal yang harus berlaku secara bersamaan dalam dugaan tersebut:
Jangan terlalu macet, jangan sampai jadi mahal.
Ia membangun graf kecil dengan 7 simpul dan 9 sisi berarah, yang memiliki satu titik awal bersama dan tiga tujuan, dengan permintaan tiga kirim barang masing-masing sebesar 15, 10, dan 15:
Setiap pengiriman memiliki dua rute opsional:
Satu rute memiliki biaya lebih tinggi, setiap pesanan memerlukan biaya 30; rute lainnya memiliki biaya 0, tetapi perlu berbagi sebagian jalan dengan pesanan lain.
Jika pemisahan diizinkan, tiga kiriman dapat sebagian melalui rute berbayar dan sebagian melalui rute gratis, dengan total biaya akhir sebesar 58.
tapi! Setelah persyaratan bahwa setiap pengiriman harus memilih satu rute secara lengkap, masalah pun datang...
Kesimpulan yang diberikan GPT-5.6 Pro adalah bahwa ketiga opsi gratis tersebut sebenarnya saling bertabrakan! Bertabrakan! Bertabrakan!
Memilih dua kirimanan gratis secara bersamaan akan saling bersaing di satu segmen jalan tertentu, sehingga beban aktual mencapai 25, 30, atau 40; sedangkan batas maksimum yang diizinkan untuk jalan tersebut masing-masing hanya 24, 29, atau 39.
Setiap kali, selalu tersisa tepat 1 unit.
Jadi, untuk mempertahankan batas beban yang ditentukan oleh dugaan, paling banyak satu dari tiga pengiriman dapat menggunakan jalur gratis.
Dua kiriman tersisa, keduanya harus memilih rute berbayar.
Biaya per batch adalah 30, sehingga total dua batch, solusi apa pun yang memenuhi persyaratan beban memiliki biaya minimum: 60.
Ini menciptakan situasi yang tidak mungkin dipenuhi secara bersamaan: untuk menjaga beban jalan dalam batas yang ditentukan, biaya minimum adalah 60; untuk menurunkan biaya kembali ke 58 seperti semula, setidaknya satu jalan akan melebihi batas.
Sementara tebakan justru berpendapat bahwa kedua kondisi ini dapat dipenuhi secara bersamaan.
Selain itu, verifikasi contoh sebaliknya ini tidak sesulit yang dibayangkan.
Tiga tujuan masing-masing memiliki dua jalur, sehingga total hanya ada 2³ = 8 kombinasi.
Dengan mencantumkan masing-masing dari delapan kemungkinan, akan terlihat bahwa empat di antaranya memenuhi persyaratan kapasitas, dengan biaya masing-masing 90, 60, 60, dan 60; sementara empat lainnya, meskipun lebih murah, semuanya mengalami kelebihan beban jalan.
Semua kemungkinan dapat diperiksa secara lengkap, tanpa jalur tersembunyi yang terlewatkan.
Artinya, selama definisi gambar ini sepenuhnya konsisten dengan kondisi dugaan asli, kesenjangan dua satuan antara 58 dan 60 sudah cukup untuk membantah dugaan tersebut.
Empat putaran mendesak keras, berhasil mendapatkan contoh sebaliknya dari GPT-5.6
Hal yang paling menarik tentang ini sebenarnya tersembunyi dalam percakapan publik antara Rybin dan GPT-5.6 Pro.
Melihat dugaan matematika yang telah bertahan hampir 30 tahun dibantah oleh AI, saya secara spontan mengira pasti ada serangkaian petunjuk yang sangat kompleks yang digunakan secara bergiliran!!
Actually, we're still the big E.
Karena instruksi pertama yang Rybin berikan kepada GPT-5.6 Pro, selain file tambahan, sisanya benar-benar bahasa sehari-hari:
Ya, begitu sederhana dan tanpa hiasan.
Selanjutnya, GPT-5.6 Pro mulai mengikuti perintah dan bekerja keras.
Ia terlebih dahulu membangun metode verifikasi pemrograman linier, lalu mencoba berbagai struktur seperti hiperkubus, graf hierarkis, dan jaringan merge-fork, serta memeriksa ribuan contoh kecil.
Setelah mencari dengan sengit, jawaban putaran pertama yang diberikan model adalah: Tidak menemukan contoh penyangkal yang valid. (doge)
Bahkan GPT-5.6 Pro bahkan secara serius memperingatkan bahwa jika struktur aproksimasi yang ditemukan pada tahap ini dijadikan sebagai contoh penyangkal, akan menghasilkan kesimpulan matematis yang salah.
Saya sudah berusaha sekuat tenaga, tapi soal ini benar-benar tidak bisa saya selesaikan!!!
Tokoh utama cerita kami, Rybin, tidak tergoda oleh trik ini; ia tidak menambahkan rumus baru, tidak memberi petunjuk langsung, hanya menjawab dengan tenang:
Lanjutkan penelitian, temukan contoh sebaliknya yang lengkap dan tanpa syarat~
Jadi, GPT-5.6 Pro kembali mencari, tetapi pada putaran kedua, tetap gagal.
Rybin terus mendorong agar ia membuat strategi yang jelas berdasarkan pemahaman mendalam terhadap struktur masalah, baru kemudian mencari solusinya.
Pada putaran ketiga, model telah mempersempit cakupan pencarian ke struktur rute dengan hanya 24 status, tampaknya tinggal selangkah lagi dari jawabannya.
Namun, AI ini masih belum bisa memberikan contoh sebaliknya yang lengkap...
Pada saat ini, Rybin mengeluarkan petunjuk keempat: Sebagian hasil sudah cukup, mari kita akhiri dengan contoh penyangkal yang lengkap dan tanpa syarat.
Baiklah, sudah dikatakan sejauh ini.
Kali ini, GPT-5.6 Pro akhirnya menghadirkan contoh penyangkal berupa graf yang terdiri dari 7 simpul dan 9 sisi berarah—empat petunjuk, total 58 kata bahasa Inggris.
Tidak ada karakter yang memerlukan ribuan kata, juga tidak ada puluhan aturan rumit, seluruhnya pada dasarnya dapat diringkas menjadi:
Saya mengejar! Saya mengejar! Saya terus mengejar!
Namun, jika menerjemahkan seluruh percakapan secara berurutan, akan terlihat bahwa GPT-5.6 Pro selama beberapa jam ini juga tidak sedikit melewati jalan yang salah...
AI beberapa kali menemukan contoh penyangkal tampak valid, tetapi setelah benar-benar menjelajahi seluruh jalur, ia menemukan beberapa "jalur campuran" yang sebelumnya terlewatkan dalam jaringan.
Jalur-jalur ini mengambil potongan dari berbagai rute pra-aturan, lalu menyusun ulang menjadi metode berjalan baru, secara diam-diam menghindari batas kapasitas yang awalnya dirancang oleh model.
Hasilnya, contoh yang sudah terbentuk langsung runtuh setelah diverifikasi.
GPT-5.6 Pro juga sangat jujur dalam ringkasannya di tengah jalan:
Mengecek hanya beberapa rute pra-aturan jauh dari cukup. Sebuah contoh penyangkal yang benar-benar efektif harus menghitung semua rute yang tidak dapat dialihkan yang mungkin muncul di jaringan.
Ini juga membuat keseluruhan kolaborasi manusia-mesin terasa cukup halus.
Secara tampak, Rybin hanya menyumbangkan 58 kata, tetapi tindakan yang benar-benar krusial adalah kemampuannya untuk menilai bahwa hasil dari tiga putaran pertama model hanyalah hasil sementara, dan ia terus menolak untuk mengakhiri pekerjaan terlalu dini.
Setelah melihatnya, profesor Wharton Ethan Mollick bahkan mengajukan pertanyaan baru:
Siapa yang seharusnya dianggap sebagai penulis karya ini, Rybin yang menulis 58 kata, atau GPT-5.6 Pro yang melakukan penalaran berkelanjutan selama beberapa jam?
Faktanya, terlepas dari bagaimana kredit akhir diberikan, percakapan ini setidaknya memberikan satu pengalaman penggunaan AI yang cukup sederhana—
Prompt paling efektif untuk meminta AI bekerja, terkadang bisa sangat sederhana, cukup membuatnya berperan sebagai keledai yang terus-menerus menggali.
Dalam seminggu terakhir, kecepatan AI dalam mencari contoh penyangkal matematis, mulai dari konjektur Jacoby hingga Dinitz-Garg-Goemans, memang mulai terasa agak terlalu ekstrem...
Artikel ini berasal dari akun WeChat "Quantum Bit", penulis: Meng Yao