Komputasi & AIPracetakTeori3 menit baca

MENGURUTKAN DENGAN PERBANDINGAN TERLARANG, HAMPIR SAMA CEPATNYA

Untuk menyusun n item secara berurutan dengan membandingkannya dua demi dua, sekitar n log n perbandingan diperlukan sekaligus mencukupi. Tetapi itu mengandaikan dua item mana pun dapat dibandingkan.

Sering kali tidak demikian. Para penulis meminjam sebuah contoh dari makalah tahun 2011: beberapa kandidat melamar pekerjaan yang sama, masing-masing dengan pemberi referensi. Dua kandidat hanya dapat dibandingkan jika ada pemberi referensi yang mengenal keduanya. Perbandingan yang diizinkan membentuk sebuah jaringan, sebuah graf: setiap item adalah sebuah titik, setiap perbandingan yang diizinkan adalah sebuah sambungan. Urutan yang sebenarnya tersembunyi, tetapi graf itu dijamin memuatnya, sebagai sebuah lintasan yang menghubungkan setiap item dengan item berikutnya. Pertanyaannya: berapa banyak perbandingan yang diperlukan untuk menemukan kembali urutan itu? Inilah pengurutan umum (generalized sorting).

Mengapa trik-trik biasa gagal

Algoritma-algoritma klasik bergantung pada kebebasan memilih. QuickSort memilih sebuah “pivot” dan membandingkannya dengan sebagian besar item lain, tetapi graf sembarang mungkin tidak memiliki satu item pun yang terhubung dengan sebagian besar item lainnya. MergeSort membagi item-item ke dalam kelompok dan mengurutkan masing-masing, tetapi sebuah kelompok mungkin tidak dapat diurutkan secara mandiri: dua item yang bertetangga dalam urutan akhir belum tentu terhubung di dalam kelompok itu. Lebih mendasar lagi, pengurutan biasa selalu menyediakan suatu perbandingan yang menyingkirkan bagian yang cukup besar dari urutan-urutan yang mungkin; dengan perbandingan yang dibatasi, perbandingan semacam itu mungkin tidak ada sama sekali.

Kemajuan berjalan lambat. Pada 2011, Zhiyi Huang, Sampath Kannan, dan Sanjeev Khanna menemukan sebuah metode yang menggunakan sekitar n¹·⁵ perbandingan, dengan mengabaikan faktor-faktor logaritmik, dan batas itu bertahan untuk graf sembarang sejak saat itu. Mereka bahkan bertanya apakah masalah ini mungkin secara fundamental lebih sulit daripada pengurutan biasa, sehingga memerlukan n yang dipangkatkan dengan eksponen di atas 1.

Tebak dulu, perbaiki kemudian

Sanjeev Khanna, dari New York University, Aaron Putterman, dari Harvard University, dan Junkai Song, juga dari New York University, kini menjawab pertanyaan itu: tidak. Algoritma acak mereka mengurutkan dengan sekitar n log⁴ n perbandingan secara rata-rata, pada graf apa pun — hanya beberapa faktor logaritmik di atas pengurutan biasa. Dan, tulis mereka, algoritma itu “relatif sederhana”. Namun keunggulannya bersifat teoretis: konstanta dalam buktinya sangat besar (faktor seperti 2³²), sehingga keunggulan itu baru tampak untuk n yang sangat besar.

Algoritma ini dibangun di atas sebuah hasil yang sudah dikenal: jika seseorang memberi Anda tebakan arah setiap sambungan, yang salah pada w di antaranya, urutan dapat ditemukan kembali dengan sekitar n log n + w perbandingan. Jadi tugasnya menjadi menghasilkan tebakan dengan sedikit kesalahan menggunakan sedikit perbandingan. Langkah-langkah kuncinya:

  • Tebakan awal yang kasar. Bandingkan sampel acak pasangan-pasangan yang terhubung dan pilih urutan apa pun yang konsisten dengan jawabannya. Tebakan ini mengandung banyak kesalahan, tetapi tidak terlalu banyak.
  • Isolasi kesalahan, alih-alih memperbaikinya. Alih-alih mengoreksi tebakan yang salah, algoritma ini mencari bagian-bagian graf tempat kesalahan lebih padat daripada rata-rata dan menyisihkannya. Setiap putaran memangkas sisa kesalahan, dalam nilai harapan, dengan faktor empat.
  • Kembali lagi nanti. Sambungan-sambungan yang disisihkan ditangani pada fase berikutnya. Setiap fase menuntaskan setidaknya separuh sambungan yang masih tertunda, sehingga sekitar dua puluh fase sudah cukup untuk sejuta sambungan.

Bukti yang ditemukan bersama mesin

Pernyataan makalah ini tentang penggunaan AI luar biasa rinci. Makalah itu menyatakan bahwa ChatGPT 6-Astra “esensial dalam membuktikan batas-batas yang lebih baik”. Sebuah model mula-mula menemukan algoritma yang menggunakan sekitar n¹·³³ perbandingan, lalu macet. Para penulis mendorongnya hingga n¹·²; kemudian, setelah diberi perintah puluhan kali selama beberapa minggu, model-model menemukan perbaikan beruntun — n^(10/9), n^(17/16), n^(19/18) — sebelum mencapai algoritma yang hampir linear. Para penulis menambahkan bahwa tidak jelas apakah langkah antara mereka sendiri esensial bagi penemuan akhir itu.

Yang masih terbuka

Hasil ini menghitung perbandingan, bukan waktu komputasi: sebagaimana dinyatakan, algoritma ini tidak berjalan dalam waktu polinomial, sedangkan metode tahun 2011 berjalan dalam waktu polinomial. Para penulis mendaftar tiga pertanyaan terbuka: apakah faktor-faktor logaritmik yang tersisa dapat dihilangkan, apakah algoritma tanpa keacakan dapat bekerja sama baiknya, dan apakah algoritma yang efisien dapat mencapai jumlah perbandingan yang sama — atau bahkan sekadar mengalahkan n¹·⁵.