Komputasi & AIPracetakTeori3 menit baca

BATAS KECEPATAN UNTUK MENEMUKAN KLIK RUNTUH SETELAH 40 TAHUN

Bayangkan sebuah jejaring sosial dengan n orang. Adakah sekelompok k orang di antara mereka yang semuanya saling mengenal? Ilmuwan komputer menyebut kelompok semacam itu sebuah k-klik (k-clique), dan menemukannya adalah masalah klasik dengan penerapan yang tak terhitung banyaknya. Pendekatan naif memeriksa setiap kemungkinan kelompok berisi k orang, kira-kira sebanyak n^k — mustahil untuk jaringan besar.

Trik tahun 1985 dan tantangan panjang

Lebih dari 40 tahun yang lalu, Jaroslav Nešetřil dan Svatopluk Poljak menemukan sebuah jalan pintas. Mereka mengubah pencarian k-klik menjadi pencarian segitiga dalam sebuah graf yang lebih besar, yang pada gilirannya dapat dilakukan dengan mengalikan matriks, tabel-tabel angka yang besar. Biayanya bergantung pada ω, eksponen perkalian matriks: metode mereka memerlukan sekitar n^(ωk/3) langkah. Tak seorang pun mengetahui nilai ω secara tepat. Nilainya setidaknya 2, dan makalah itu mengutip sebuah batas atas terbaru sebesar 9/4.

Eksponen metode tahun 1985 itu tidak pernah dikalahkan. Pada 2004, Gerhard Woeginger menantang para peneliti untuk melakukan lebih baik untuk suatu k tetap; lebih dari dua dekade berlalu. Sementara itu, Hipotesis k-Klik (k-Clique Hypothesis) — bahwa n^(ωk/3) pada dasarnya adalah yang terbaik yang mungkin — menjadi fondasi “kompleksitas berbutir halus” (fine-grained complexity). Para peneliti menggunakannya untuk berargumen bahwa banyak masalah lain, dari mengurai tata bahasa hingga menganalisis data terkompresi, juga tidak dapat diselesaikan lebih cepat.

Sasaran yang bergerak

Membantah hipotesis ini memiliki kesulitan khusus. Biaya yang diprediksinya bergantung pada ω, yang tidak diketahui. Sebuah algoritma yang mengalahkan nilai ω terbaik saat ini bisa berhenti mengalahkan hipotesis itu jika seseorang kelak menemukan perkalian matriks yang lebih cepat.

Virginia Vassilevska Williams, dari MIT, dan Or Zamir, dari Universitas Tel Aviv, mengelak dari masalah itu. Mereka membuktikan bahwa untuk setiap k yang cukup besar, sebuah k-klik dapat ditemukan — bahkan dihitung jumlahnya — dalam sekitar n^((ω/3 − c)k) langkah, dengan c sebuah konstanta positif yang tidak bergantung pada k maupun ω. Penghematannya diukur terhadap nilai ω yang sebenarnya, berapa pun nilainya nanti. Penghematan itu tetap bertahan bahkan jika ω = 2, kasus terbaik yang bisa dibayangkan.

Melipat sebuah baji

Inti metode ini menyangkut pola-pola sembilan simpul. Pendekatan standar membaginya menjadi tiga kelompok berisi tiga simpul dan mengalikan tiga matriks raksasa. Para penulis melihat sebuah baji (wedge) — dua sisi yang berbagi satu simpul — dan menyisipkan, di antara dua matriks itu, sebuah tabel yang tidak mengubah apa pun: matriks identitas. Mereka lalu menuliskan identitas itu sebagai jumlah dari beberapa “pertukaran” (swaps), yang masing-masing menggabungkan kedua sisi baji menjadi satu, ditambah sebuah sisa berperingkat rendah.

Pertukaran-pertukaran itu menghasilkan pola-pola yang lebih sederhana dengan lebih sedikit sisi, yang ditangani lagi dengan metode yang sama; sebuah pola sembilan simpul memiliki paling banyak 36 sisi, sehingga rekursinya berakhir. Sisa berperingkat rendah itu mengecilkan matriks yang harus dikalikan. Menerapkan trik ini pada dua baji terpisah sekaligus itulah yang mempertahankan keunggulan bahkan ketika ω = 2. Setiap k yang merupakan kelipatan sembilan kemudian dapat dikelompokkan ke dalam sembilan blok.

Nyata tetapi sangat kecil

Para penulis tidak memberikan angka untuk keunggulan itu. Mereka menggambarkan konstanta-konstantanya berkisar “antara mikroskopis tanpa optimisasi hingga sangat kecil dengan optimisasi yang signifikan”. Intinya bukan kecepatan dalam praktik: intinya adalah bahwa sebuah penghalang yang diyakini selama puluhan tahun ternyata tidak ada.

Konsekuensinya menjangkau lebih jauh dari klik. Algoritma eksak untuk masalah optimisasi sulit seperti Max-Cut dan Max-2-SAT, yang berjalan dalam sekitar 2^(ωn/3) langkah untuk n variabel, kini juga mendapat eksponen yang lebih kecil. Begitu pula penghitungan salinan dari graf kecil tetap mana pun.

Apa yang dilakukan AI

Dalam sebuah bagian khusus, para penulis menjelaskan bagaimana mereka bekerja dengan ChatGPT-6, yang digunakan melalui antarmuka web publiknya. Berangkat dari ide-ide mereka sendiri untuk klik lima orang dan dari sebuah hasil OpenAI baru-baru ini yang membantah sebuah dugaan lain, yaitu Hipotesis Waktu Eksponensial (Exponential Time Hypothesis), model itu menemukan sebuah perbaikan pertama yang rumit untuk 5-klik. Para penulis kemudian menyarikannya, dengan bantuan AI, menjadi dekomposisi aljabar yang menjadi inti pembuktian, yang mereka pandang sebagai “hampir murni kontribusi AI”. Kerangka algoritmik yang dibangun di sekitarnya, menurut mereka, sebagian besar adalah karya mereka sendiri.

Satu catatan menonjol. Bukti-bukti kabur yang dihasilkan AI sulit dibaca manusia, catat para penulis — dan mereka “terkesan bahwa bukti-bukti itu juga sulit dipahami oleh AI itu sendiri”.