Komputasi & AI · eksperimennya
Kalahkan batasnya
Sebuah jaringan, sekelompok orang yang semuanya saling mengenal, sebuah jalan pintas tahun 1985 melalui perkalian matriks, dan sebuah hipotesis yang bertahan selama puluhan tahun. Empat pertanyaan, dari pemula hingga mahir, tentang berakhirnya Hipotesis k-Klik.
1 · Nyatakan apa yang dibuktikan
Pemula
Apa yang ditunjukkan artikel tentang Hipotesis k-Klik?
2 · Hitung biaya tahun 1985
Metode Nešetřil–Poljak menemukan sebuah k-klik dalam sekitar n^(ωk/3) langkah. Ambil k = 9 dan ω = 2, nilai terendah yang mungkin bagi ω.
Menengah
Eksponen n berapa yang dihasilkan metode tahun 1985 itu?
3 · Jelaskan “bahkan jika ω = 2”
Hipotesis itu memprediksi biaya sebesar n^(ωk/3). Nilai ω yang tepat tidak diketahui: nilainya setidaknya 2, dan artikel mengutip batas atas sebesar 9/4.
Mahir
Mengapa penting bahwa penghematan baru itu berlaku berapa pun nilai ω, bahkan ω = 2?
4 · Bawa keunggulannya lebih jauh
Max-2-CSP, yang mencakup Max-Cut dan Max-2-SAT, pada n variabel Boolean, sebelumnya diselesaikan dalam sekitar 2^(ωn/3) langkah. Bagi variabel-variabel itu menjadi sembilan kelompok, dan setiap penugasan nilai sebuah kelompok menjadi simpul dalam masalah 9-klik berbobot.
Mahir
Apa yang dihasilkan algoritma klik yang baru untuk masalah-masalah ini?
Batas terkalahkan
—