AI Membantah Hipotesis Waktu Eksponensial: Apa Artinya Semua Ini

OpenAI dan Anthropic masing-masing menerbitkan sebuah pembuktian bahwa hipotesis waktu eksponensial itu salah.

ETH adalah asumsi berusia 27 tahun dalam ilmu komputer teoretis yang menyatakan beberapa masalah tidak akan pernah bisa diselesaikan jauh lebih cepat daripada brute force. Kini, dua laboratorium AI teratas mengatakan itu tidak benar.

Jika pembuktian ini bertahan, ini adalah hasil paling signifikan yang dihasilkan AI dalam ilmu komputer sejauh ini. Ini juga memaksa peninjauan ulang terhadap ratusan makalah penelitian yang secara harfiah mengasumsikan ETH benar.

Dalam artikel ini, kami menjelaskan apa sebenarnya arti hipotesis waktu eksponensial, bersama dengan P vs. NP yang terkait. Kami juga akan melihat apa tepatnya klaim kedua lab, bagaimana pembuktian diperiksa, dan apa yang (dan yang tidak) berubah untuk kriptografi.

P vs. NP dalam Bahasa Sederhana

P versus NP menanyakan apakah setiap masalah yang jawabannya mudah diperiksa juga mudah diselesaikan. Ini adalah salah satu dari tujuh Masalah Hadiah Milenium, dan tetap terbuka setelah kabar ini.

Teka-teki Sudoku adalah ilustrasi klasik. Memeriksa kisi yang sudah terisi butuh hitungan detik: pindai setiap baris, kolom, dan kotak untuk melihat pengulangan. Menemukan solusi dari kisi yang masih kosong sebagian bisa butuh waktu jauh lebih lama, dan kesenjangannya meledak seiring ukuran kisi bertambah.

• P adalah kelas masalah yang dapat diselesaikan komputer dalam waktu polinomial, artinya beban kerja bertambah seperti n^², n^³, dan seterusnya saat ukuran masukan n tumbuh.
• NP adalah kelas masalah yang usulan solusinya dapat diverifikasi komputer dalam waktu polinomial.

Setiap masalah dalam P juga berada di NP. Pertanyaan terbukanya adalah apakah sebaliknya berlaku. Kebanyakan ilmuwan komputer meyakini P ≠ NP, sehingga beberapa masalah pada dasarnya lebih sulit untuk diselesaikan daripada diperiksa. Kriptografi modern bertumpu pada keyakinan itu: mengenkripsi itu mudah, tetapi membongkar enkripsi tanpa kunci seharusnya sulit.

Apa Itu Hipotesis Waktu Eksponensial?

ETH lebih tajam: ia mengklaim bahwa satu masalah NP tertentu, 3-SAT, memerlukan waktu eksponensial tak peduli secerdas apa pun algoritmenya. Russell Impagliazzo dan Ramamohan Paturi dari UC San Diego mengusulkannya pada akhir 1990-an, dengan Francis Zane berkontribusi pada karya dasar.

Masalah 3-SAT

Dalam 3-SAT, Anda mendapat sebuah rumus yang terdiri dari n variabel benar/salah dan daftar klausa. Setiap klausa menggabungkan tiga kondisi dengan OR, misalnya "x₁ benar ATAU x₄ salah ATAU x₇ benar." Tugasnya adalah menemukan pengaturan variabel yang memuaskan setiap klausa sekaligus.

Brute force mencoba semua 2ⁿ pengaturan, sehingga setiap variabel tambahan menggandakan pekerjaan. Anda bisa melihat bahwa di sekitar 100 variabel hal itu tidak ada harapan.

Apa yang dikatakan ETH

ETH menyatakan ada suatu konstanta c > 1 sehingga tidak ada algoritme yang menyelesaikan 3-SAT lebih cepat daripada cⁿ. Algoritme cerdas bisa mengecilkan basisnya di bawah 2, tetapi tidak pernah turun sampai sesuatu yang subeksponensial. Secara formal: terdapat δ > 0 sehingga 3-SAT tidak dapat diselesaikan dalam waktu O(2^δn).

Selama beberapa dekade, kemajuan sesuai dengan gambaran itu. Para peneliti terus memangkas basisnya, tetapi tetap jauh di atas 1. Karena 3-SAT dapat diubah menjadi banyak masalah lain, ETH menjadi asumsi andalan. Para peneliti menggunakannya untuk berargumen bahwa masalah seperti Clique, Vertex Cover, Independent Set, dan lainnya juga tidak bisa diselesaikan jauh lebih cepat. 

Bagaimana hasil baru dibandingkan

Batas baru ini ditulis singkat sebagai 2^o(n). Biaya per variabel tambahan menyusut menuju 1 seiring n bertambah, persis seperti yang dikatakan ETH mustahil.

Apa yang Diumumkan OpenAI dan Anthropic

Kedua lab secara independen mencapai batas subeksponensial yang pada dasarnya sama, dan keduanya mendukung makalahnya dengan bukti yang diperiksa mesin di asisten pembuktian Lean.

Anthropic mengatakan Claude menemukan algoritme inti tanpa masukan manusia setelah menghasilkan sekitar 14 juta token keluaran. Metodenya menggunakan jaringan tensor dan argumen rank. Para peneliti kemudian membantu penulisan makalah akhir.

Mengapa kedua lab menemukannya pada hari yang sama?

Kedua lab belum menjelaskan soal waktu tersebut. Makalah Anthropic menyebut kedua hasil itu independen dan bersamaan, dan kedua tulisan menempuh jalur matematika berbeda untuk mencapai batas yang pada dasarnya sama. 

Sejumlah konteks membuat tumpang tindih ini kurang mengejutkan daripada kelihatannya. Kedua lab telah mengarahkan model mereka pada daftar panjang masalah terbuka, dan OpenAI saja merilis ratusan naskah matematika yang dihasilkan AI pada awal Oktober. ETH adalah salah satu target paling dikenal di bidang ini, dan kedua model belajar dari riset terpublikasi yang sama. Penemuan independen dan simultan juga merupakan pola lama dalam sains, seperti Newton dan Leibniz pada kalkulus atau Darwin dan Wallace pada seleksi alam.

Seberapa solid pembuktiannya?

Lean mengonfirmasi bahwa pernyataan formal mengikuti secara logis dari aksiomanya. Ia tidak dapat mengonfirmasi bahwa pernyataan formal mengatakan hal yang sama dengan makalah. Anthropic mencatat tidak ada mesin yang memeriksa kesesuaian ini, dan OpenAI mengatakan berkas Lean-nya membuktikan batas yang sedikit lebih lemah daripada tajuk utamanya.

Sekarang, para peneliti yang mengusulkan masalah ini, Impagliazzo dan Paturi, bersama Ryan Williams dari MIT, sedang menyelenggarakan lokakarya untuk menilai apakah pernyataan formal itu benar-benar menangkap ETH. Surat mereka menekankan bahwa berpartisipasi dalam peninjauan bukanlah bentuk dukungan. Hingga saat ini, saat artikel ditulis, belum ada yang secara publik menemukan cacat. 

Williams mengatakan bagian-bagian dari bukti OpenAI terlihat rutin, sementara "dua atau tiga bagian yang terlihat asing" masih perlu ditelaah. Impagliazzo, salah satu penulis ETH, menggambarkan hasil ini sangat mengejutkan.

Apa yang Berubah dan Apa yang Tidak

Dalam praktiknya, hampir tidak ada yang berubah hari ini (untungnya): algoritme baru hanya mengalahkan brute force pada masukan yang jauh lebih besar daripada apa pun yang bisa ditampung komputer.

Tidak ada pemecah SAT yang lebih cepat

Makalah Anthropic mengatakan metodenya hanya mengalahkan brute force pada masukan yang luar biasa besar. Untuk rumus khas dengan lima klausa per variabel, titik perpotongannya adalah sebuah angka dengan sekitar 10.000 digit. Dalam kasus paling umum, itu adalah angka dengan kira-kira 100 juta digit. 

Para penulis juga mengatakan pendekatan mereka kecil kemungkinannya membantu pada apa pun di bawah sekitar 10 juta variabel. Pemecah SAT yang digunakan dalam verifikasi chip, penjadwalan, dan perencanaan tidak akan menjadi lebih cepat dari hasil ini.

Kriptografi tidak rusak

Hasil ini tidak menyentuh P vs NP. Tidak ada yang berpura-pura demikian. OpenAI mengatakan telah memeriksa apakah algoritmenya merusak kriptosistem nyata dan cukup yakin tidak. 

Teori ditulis ulang

Dampak terbesar ada pada penelitian. Hasil kekerasan komputasi yang dibangun di atas ETH atau SETH kini butuh pijakan baru, dan beberapa peneliti mengatakan bertahun-tahun pekerjaan mereka sendiri mungkin perlu ditinjau ulang. Namun tidak semuanya runtuh. Anthropic mencatat hasil ini tidak membantah masalah vektor ortogonal, yang mendukung banyak hasil kompleksitas berbutir halus. 

Mengapa Ini Penting bagi AI

Tajuk utamanya kurang tentang 3-SAT dan lebih tentang siapa yang menemukan jawabannya: dua sistem AI secara independen menggulingkan sebuah dugaan yang dipercaya para pakar manusia selama satu generasi.

AI sebagai kolaborator riset

Para peneliti kini menggambarkan hasil AI baru mendarat setiap satu atau dua minggu, mengganggu proyek yang sedang berjalan. Alat formal seperti Lean menjadi sentral karena memungkinkan manusia memercayai bukti panjang yang ditulis mesin tanpa menurunkan ulang setiap baris.

Jalur pintas tersembunyi dan peningkatan diri

ETH menangkap keyakinan bahwa beberapa masalah pencarian tidak punya jalan pintas cerdik. Jika keyakinan itu salah, masalah-masalah yang jelas-jelas sulit lainnya mungkin juga menyimpan jalan pintas.

Saya memikirkan penemuan algoritme sebagai salah satu area di mana jalan pintas seperti itu bisa sangat berarti bagi peningkatan diri rekursif, yaitu gagasan tentang sistem AI yang membantu merancang AI yang lebih baik. Menggunakan AI untuk menemukan algoritme yang lebih cepat adalah salah satu jalur konkret ke arah itu, meskipun tidak ada dalam hasil ini yang langsung melakukan hal tersebut hari ini.

Apa artinya bagi praktisi data

Bagi orang yang membangun dengan data, tiga pelajaran menonjol:

• Teori kompleksitas bukan sekadar akademis: Mengetahui mengapa suatu masalah NP-sulit memberi tahu Anda kapan harus memikirkan heuristik, pendekatan komputasi hampiran, atau solver alih-alih pencarian eksak.
• Verifikasi adalah keterampilan: Saat AI menghasilkan lebih banyak kode dan analisis, memeriksa keluarannya (dengan pengujian, bukti, atau pipeline yang dapat direproduksi) sama pentingnya dengan memproduksinya.
• Asimtotik bisa menyesatkan: Algoritme yang "lebih cepat" dalam teori bisa tidak berguna pada ukuran dunia nyata. 

Kesimpulan

Jika pembuktian lolos tinjauan pakar, hipotesis waktu eksponensial akan bergabung dengan daftar singkat dugaan yang banyak dipercaya tetapi ternyata salah (seperti dugaan jumlah pangkat Euler). Namun P vs NP tetap terbuka dan kriptografi untuk saat ini aman.

Tonggak berikut yang perlu diperhatikan adalah lokakarya tinjauan yang dipimpin oleh para penulis asli ETH, implementasi ulang algoritme secara independen, dan apakah ada yang memperketat batasnya lebih jauh.

Untuk membangun fondasi di balik kisah seperti ini, jelajahi kursus kami tentang struktur data dan algoritme, pemrograman Python, dan pembelajaran mesin. Kursus-kursus ini membahas pemikiran Big-O yang membuat hasil seperti ini dapat dibaca.