Itu adalah batasan yang cukup ketat, jadi tidak terlihat bahwa memori tambahan bisa pernah terbukti bermanfaat. Tapi untuk kejutan mereka, Buhrman dan Cleve menunjukkan bahwa jika Anda mengubah bit dengan cara yang tepat, Anda benar-benar bisa mendapatkan kekuatan komputasi tambahan dari memori penuh.
“Itu adalah kejutan bagi semua orang,” kata Loff, yang saat itu adalah mahasiswa pascasarjana di kelompok Buhrman, bekerja pada pertanyaan memori dengan rekan mahasiswa lainnya, Florian Speelman. Tim segera memperluas hasil tersebut ke kelas masalah yang lebih besar, dan menerbitkan hasil gabungan mereka pada tahun 2014.
Mereka menamai kerangka kerja baru itu komputasi katalitik, meminjam istilah dari kimia. “Tanpa katalis, reaksi tidak akan berlanjut,” kata Raghunath Tewari, seorang teoritis kompleksitas di Institut Teknologi India, Kanpur. “Tapi katalis itu sendiri tetap tidak berubah.”
Tidak Jauh Dari Pohon
Sebuah kelompok kecil peneliti terus mengembangkan komputasi katalitik lebih lanjut, tetapi tidak ada yang bahkan mencoba menerapkannya pada masalah evaluasi pohon yang awalnya mengilhami pencarian Koucký. Untuk masalah tersebut, pertanyaan terbuka yang tersisa adalah apakah sejumlah kecil memori dapat digunakan untuk penyimpanan dan komputasi secara bersamaan. Tapi teknik komputasi katalitik bergantung pada memori penuh tambahan yang sangat besar. Perkecil memori tersebut dan teknik tersebut tidak lagi berfungsi.
Namun, seorang peneliti muda tidak bisa tidak bertanya-tanya apakah ada cara untuk menyesuaikan teknik tersebut untuk menggunakan kembali memori dalam algoritma evaluasi pohon. Namanya James Cook, dan bagi dia masalah evaluasi pohon itu pribadi: Stephen Cook, teoritis kompleksitas legendaris yang menemukan masalah itu, adalah ayahnya. James bahkan telah bekerja pada masalah tersebut di sekolah pascasarjana, meskipun dia sebagian besar fokus pada subjek yang sama sekali tidak terkait. Ketika dia menemui makalah komputasi katalitik asli pada tahun 2014, James hampir lulus dan meninggalkan dunia akademis untuk teknik perangkat lunak. Tapi bahkan saat dia menetap dalam pekerjaan baru, dia terus berpikir tentang komputasi katalitik.
“Saya harus memahaminya dan melihat apa yang bisa dilakukan,” katanya.
Selama bertahun-tahun, James Cook mencoba-coba dengan pendekatan katalitik untuk masalah evaluasi pohon pada waktu luangnya. Dia memberikan ceramah tentang kemajuannya pada sebuah simposium tahun 2019 untuk menghormati karya ayahnya dalam teori kompleksitas. Setelah ceramah, dia didekati oleh seorang mahasiswa pascasarjana bernama Ian Mertz, yang jatuh cinta dengan komputasi katalitik lima tahun sebelumnya setelah belajar tentangnya sebagai mahasiswa pascasarjana yang mudah terkesan.
“Situasinya seperti bayi burung yang mencetak skenario,” kata Mertz.
James Cook dan Ian Mertz mengadaptasi teknik komputasi katalitik untuk merancang algoritma memori rendah untuk masalah evaluasi pohon.
Foto: Colin Morris/Quanta Magazine
Foto: Stefan Grosser/Quanta Magazine
Cook dan Mertz bergabung, dan upaya mereka segera membuahkan hasil. Pada tahun 2020, mereka merancang sebuah algoritma yang memecahkan masalah evaluasi pohon dengan memori lebih sedikit daripada minimum yang diperlukan yang dikonseptualisasikan oleh Cook dan McKenzie—meskipun hanya sedikit di bawah ambang batas tersebut. Namun, itu sudah cukup untuk menarik taruhan $100; untungnya bagi keluarga Cook, separuhnya tetap di dalam keluarga.
Tapi masih ada pekerjaan yang harus dilakukan. Para peneliti telah mulai mempelajari evaluasi pohon karena tampaknya mungkin akhirnya memberikan contoh masalah dalam P yang tidak ada di L—dengan kata lain, masalah yang relatif mudah yang tidak dapat dipecahkan menggunakan memori sangat sedikit. Metode baru Cook dan Mertz menggunakan memori lebih sedikit daripada algoritma evaluasi pohon lainnya, tetapi masih menggunakan lebih banyak daripada algoritma untuk masalah dalam L. Evaluasi pohon tertekan, tapi tidak teratasi.
Pada tahun 2023, Cook dan Mertz mengeluarkan algoritma yang ditingkatkan yang menggunakan memori jauh lebih sedikit—hampir lebih dari maksimum yang diizinkan untuk masalah dalam L. Banyak peneliti sekarang menduga bahwa evaluasi pohon berada di L setelah semua, dan bahwa bukti hanya masalah waktu. Teoritis kompleksitas mungkin memerlukan pendekatan yang berbeda untuk masalah P versus L.
Sementara itu, hasil Cook dan Mertz telah membangkitkan minat dalam komputasi katalitik, dengan karya-karya baru mengeksplorasi hubungan dengan kebetulan dan efek dari memperbolehkan beberapa kesalahan dalam mengatur kembali memori penuh ke keadaan aslinya.
“Kita belum selesai menjelajahi apa yang bisa kita lakukan dengan teknik baru ini,” kata McKenzie. “Kita dapat mengharapkan lebih banyak kejutan.”
Cerita asli dicetak ulang dengan seizin dari Quanta Magazine, sebuah publikasi independen secara editorial dari Simons Foundation yang misinya adalah untuk meningkatkan pemahaman publik tentang ilmu pengetahuan dengan meliput perkembangan penelitian dan tren di bidang matematika, ilmu fisika, dan ilmu kehidupan.