Bisakah AI generatif memecahkan masalah terbesar ilmu komputer yang belum terpecahkan?

Pertanyaannya -- Apakah P=NP? -- merupakan tantangan teoretis yang besar. Para ilmuwan mengambil pendekatan ide memberi makan sendok ke GPT-4 untuk mencari jawabannya.

Ilmuwan komputer merenungkan apakah waktu yang dibutuhkan untuk menghitung suatu solusi berada di luar jangkauan masalah yang paling sulit. Pertanyaan Apakah P=NP? kini diperlakukan sebagai sesi multi-prompt dengan model bahasa GPT-4. Wawasan terbesar dari pekerjaan ini mungkin adalah bagaimana memangkas sesi obrolan sebelumnya untuk mempertahankan diskusi.

Ketika para ilmuwan komputer berkumpul di pesta koktail, mereka cenderung mengobrol, antara lain, tentang satu-satunya masalah terpenting yang belum terpecahkan dalam ilmu komputer: pertanyaan, Apakah P=NP?

Dirumuskan hampir 50 tahun yang lalu, pertanyaan apakah P sama dengan NP adalah sebuah meditasi mendalam tentang apa yang pada akhirnya dapat dicapai dengan komputer. Pertanyaan tersebut, yang memiliki implikasi pada bidang-bidang seperti kriptografi dan komputasi kuantum, belum mendapatkan jawaban yang meyakinkan meskipun telah dilakukan penelitian intensif selama beberapa dekade. Kini, upaya tersebut telah melibatkan bantuan AI generatif.

Dalam makalah berjudul "Model Bahasa Besar untuk Sains: Studi tentang P vs. NP", penulis utama Qingxiu Dong dan rekannya memprogram model bahasa besar GPT-4 OpenAI menggunakan apa yang mereka sebut Metode Socrates, beberapa putaran obrolan melalui perintah dengan GPT -4. (Makalah ini diposting bulan ini di server pra-cetak arXiv oleh para ilmuwan di Microsoft, Universitas Peking, Universitas Beihang di Beijing, dan Universitas Teknologi dan Bisnis Beijing.)

Metode tim ini adalah dengan mengambil argumen dari makalah sebelumnya dan memasukkannya ke dalam GPT-4 untuk mendapatkan respons yang bermanfaat.

Dong dan tim mengamati bahwa GPT-4 menunjukkan argumen untuk menyimpulkan bahwa P sebenarnya tidak sama dengan NP. Dan mereka mengklaim bahwa penelitian tersebut menunjukkan bahwa model bahasa yang besar dapat melakukan lebih dari sekedar mengembalikan teks dalam jumlah besar, mereka juga dapat "menemukan wawasan baru" yang dapat mengarah pada "penemuan ilmiah", sebuah prospek yang mereka namakan "LLM untuk Sains."

Untuk memahami apa yang penulis lakukan, perlu diketahui sedikit tentang masalah P=NP.

Dirumuskan secara independen pada tahun 1970-an oleh ilmuwan komputer Stephen Cook dan Leonid Levin, masalah P versus NP -- atau, "P=NP", sebagaimana sering disebut -- adalah pertanyaan tentang seberapa mudah menyelesaikan suatu masalah tertentu dengan komputer. Huruf P melambangkan permasalahan yang telah terbukti layak untuk diselesaikan, artinya waktu untuk menghitung penyelesaian tidak dapat dijangkau; dan solusinya juga mudah untuk diverifikasi, artinya memeriksa apakah jawabannya benar.

Sebaliknya, huruf NP melambangkan permasalahan yang jawabannya juga relatif mudah diverifikasi, sama seperti P, namun tidak ada cara mudah untuk menghitung solusinya. Merupakan hal yang umum untuk menyebut permainan Sudoku sebagai contoh NP: setiap permainan Sudoku yang terisi dapat dengan mudah diperiksa keakuratannya, namun tugas untuk menemukan solusi tumbuh secara eksponensial dalam hal waktu yang dibutuhkan seiring dengan semakin besarnya grid permainan. (Jika Anda ingin menyelami rincian teoretis yang berat tentang P=NP, cobalah makalah Cook tahun 2000 tentang masalah tersebut.)

Lalu masalahnya, Apakah P=NP? menanyakan apakah permasalahan yang kita anggap sulit dipecahkan, NP, namun kita tahu mudah untuk diverifikasi, ternyata bisa dengan mudah diverifikasi dan diselesaikan, seperti halnya permasalahan P.

Jawaban negatif, yaitu P tidak sama dengan NP, berarti beberapa masalah berada di luar kemampuan komputer untuk menyelesaikannya bahkan dengan anggaran komputasi yang sangat besar -- dengan kata lain, batas atas komputasi. Tantangan seperti memecahkan beberapa enkripsi akan tampak lebih berat, di luar jangkauan komputasi.

Untuk mengatasi P=NP, Dong dan tim membangun tren "penalaran" beberapa tahun terakhir dengan model bahasa yang besar. Seperti yang dicontohkan dalam karya Takeshi Kojima dan tim di Universitas Tokyo dan Google Research pada tahun 2022, kemampuan model bahasa besar pada tugas-tugas tertentu dapat ditingkatkan hanya dengan menambahkan frasa "Mari berpikir langkah demi langkah" di awal cepat, disertai dengan contoh jawaban. Ungkapan tersebut, menurut mereka, cukup untuk mendorong langkah-langkah "rantai pemikiran" pada model bahasa.

Ini adalah jenis prosedur rantai pemikiran yang sama yang dilakukan Dong dan timnya dengan Metode Sokrates mereka. Melalui 97 putaran cepat, penulis membujuk GPT-4 dengan berbagai permintaan yang memahami seluk beluk matematika P=NP, dengan mengawali setiap perintahnya dengan pernyataan awal untuk mengkondisikan GPT-4, seperti, " Anda adalah seorang filsuf yang bijaksana," "Anda adalah ahli matematika yang ahli dalam teori probabilitas" -- dengan kata lain, permainan yang sekarang sudah dikenal untuk membuat GPT-4 memainkan peran, atau, "persona" untuk menyesuaikan gaya pembuatan teksnya.

Contoh salah satu putaran obrolan dari diskusi yang sangat teoretis.

Strategi mereka adalah menginduksi GPT-4 untuk membuktikan bahwa P tidak, pada kenyataannya, sama dengan NP, dengan terlebih dahulu berasumsi bahwa P sama dengan sebuah contoh dan kemudian menemukan cara agar contoh tersebut menjadi berantakan -- sebuah pendekatan yang dikenal dengan pembuktian dengan kontradiksi.

Hal yang menarik adalah dua penulis penelitian tersebut, Ke Xu dan Guangyan Zhou, secara terpisah telah merilis makalah bulan ini di mana mereka secara langsung menjelaskan tentang P=NP dalam istilah matematika formal tradisional. Dalam makalah tersebut, mereka menyimpulkan bahwa P tidak sama dengan NP.

Apa yang dilakukan Dong, Xu, Zhou, dan tim serupa dengan merekonstruksi makalah matematika formal mereka dengan mengarahkan GPT-4 melalui bahasa penalaran mereka sendiri, cepat demi cepat. Faktanya, dari 73 halaman makalah tersebut, 67 halaman merupakan cetakan lengkap dari masing-masing 97 prompt dan respon lengkap dari GPT-4. Ini seperti latihan besar dalam rekayasa cepat untuk merekonstruksi sebuah argumen.

Sulit untuk mengatakan apakah hasil yang dicapai Dong dan tim dengan GPT-4 benar-benar membuktikan P tidak sama dengan NP karena makalah Xu dan Zhou sendiri sangat baru. Di situs Semantic Scholar yang mengumpulkan kutipan makalah, belum ada kutipan untuk makalah tersebut -- selain makalah mereka sendiri bersama Dong dan tim. Ada beberapa pembahasan makalah GPT-4 oleh berbagai pembaca yang tertarik di situs AI HuggingFace yang bisa Anda simak.

Jadi, dunia belum menerima argumen mereka.

Yang lebih penting bagi orang-orang yang menyukai Gen AI, penulis berpendapat bahwa dialog mereka menunjukkan prospek model bahasa besar untuk melakukan lebih dari sekadar meniru kreasi tekstual manusia.

“Penyelidikan kami menyoroti potensi kemampuan GPT-4 untuk berkolaborasi dengan manusia dalam mengeksplorasi masalah yang sangat kompleks dan tingkat ahli,” tulis mereka. Sepanjang 67 halaman petunjuk dan tanggapan, mereka menyoroti bagian-bagian yang mereka anggap sebagai "bagian yang berwawasan luas" dari apa yang dilontarkan GPT-4.

Seberapa mendalam tanggapan tersebut mungkin juga merupakan topik yang memerlukan penyelidikan tersendiri. Beberapa ilmuwan menemukan bahwa model bahasa berukuran besar sangat dangkal dalam merangkai kutipan dan deskripsi.

Namun, ada hal menarik yang muncul di pinggir makalah, saat Dong dan tim memberi anotasi pada balasan GPT-4 dengan pengamatan mereka tentang kualitas balasan.

Dalam salah satu catatan dalam tanda kurung tersebut, penulis menulis bahwa masing-masing tanggapan GPT-4 sebelumnya telah dimasukkan sebagai latar belakang dalam permintaan terbaru -- kecuali di mana penulis memilih untuk memangkas tanggapan agar hanya mempertahankan sebagian besar tanggapan bit yang relevan.

“Jika model memberikan banyak solusi, kami hanya menyertakan solusi paling berharga dalam riwayat percakapan,” tulis mereka di pinggir halaman 7. “Strategi ini memungkinkan GPT-4 berkonsentrasi pada informasi terkait, sehingga meningkatkan efisiensi dan efektivitasnya secara keseluruhan. ."

Dengan kata lain, ada kurasi tertentu yang bermanfaat tentang cara GPT-4 menggunakan sejarah masa lalu dalam apa yang disebut "jendela konteks", semua putaran sebelumnya yang dapat dijadikan acuan. Dong dan timnya terlibat dalam rekayasa cepat yang sangat selektif untuk memandu GPT-4 melalui rangkaian argumen. Hal ini sejalan dengan praktik "retrival-augmented generation", atau "RAG", yang merupakan minat saat ini dalam menggunakan data obrolan sebelumnya sebagai masukan baru untuk model bahasa besar.

Hal ini mungkin merupakan salah satu kontribusi paling signifikan dari keseluruhan latihan: Baik mengatasi P=NP atau tidak, sebuah batasan baru dalam rekayasa cepat dapat mendekatkan program ke RAG untuk memberikan sesi obrolan yang lebih mendalam . Jika Anda mengingat kembali sesi obrolan baru-baru ini, sesi tersebut cenderung tidak masuk akal, sering kali keluar dari topik.

Melalui 97 ronde, Dong dan tim berhasil menjaga mesinnya tetap tepat sasaran, dan ada sesuatu yang bisa dikatakan tentang hal itu.