Mengapa menambahkan hard drive penuh dapat membuat komputer lebih kuat

Versi aslinya dari cerita ini muncul di Berapa banyak majalah.

“Jelas” adalah kata yang berbahaya, bahkan dalam skenario yang tampak sederhana. Misalkan, misalnya, Anda perlu melakukan perhitungan penting. Anda dapat memilih antara dua komputer yang hampir identik, kecuali bahwa seseorang memiliki hard drive ekstra penuh dengan foto keluarga yang berharga. Wajar untuk berasumsi bahwa kedua opsi itu sama -sama baik – bahwa drive tambahan tanpa ruang yang tersisa tidak akan membantu perhitungan Anda.

“Jelas, itu tidak membantu, kan?” dikatakan Bruno Loffseorang ilmuwan komputer di University of Lisbon.

Salah. Pada tahun 2014, Loff dan empat peneliti lainnya menemukan bahwa menambahkan ruang penyimpanan penuh pada prinsipnya membuat komputer lebih kuat. Kerangka teori mereka, disebut Komputasi Katalitiktelah menjadi objek studi dengan haknya sendiri. Dan baru -baru ini, itu juga membantu para peneliti membuktikan a hasil yang mengejutkan Dalam bidang terkait ilmu komputer: pendekatan standar untuk menyelesaikan pertanyaan terbuka utama tentang peran memori dalam perhitungan kemungkinan besar merupakan jalan buntu.

“Ini cukup prestasi,” kata Pierre McKenzieahli teori kompleksitas di University of Montreal. “Saya sangat menghargai hasil ini.”

Hampir tidak ada ingatan

Komputasi katalitik tumbuh dari pekerjaan dalam teori kompleksitas komputasi, cabang ilmu komputer berfokus pada sumber daya yang diperlukan untuk menyelesaikan masalah yang berbeda. Semua masalah yang dipertimbangkan oleh teori kompleksitas dapat diselesaikan dengan prosedur langkah demi langkah yang disebut algoritma. Tetapi semua algoritma tidak dibuat sama – beberapa berjalan lebih cepat dari yang lain atau menuntut lebih sedikit ruang dalam memori komputer. Ahli teori kompleksitas mengurutkan masalah menjadi kelas yang berbeda Berdasarkan perilaku algoritma terbaik yang diketahui menyelesaikannya.

Kelas yang paling terkenal, dijuluki “P,” berisi semua masalah yang diketahui memiliki algoritma cepat, seperti menemukan angka terkecil dalam daftar atau menemukan jalur terpendek antara dua titik dalam jaringan. Kelas lain, yang disebut “L,” menetapkan bilah yang lebih tinggi untuk keanggotaan: Masalah di L harus memiliki algoritma yang tidak hanya cepat, tetapi juga menggunakan hampir tidak ada memori. Masalah “nomor terkecil dalam daftar” adalah salah satu contoh. Menurut definisi, setiap masalah di L juga ada di P, tetapi para peneliti telah lama bertanya -tanya apakah kebalikannya juga benar.

“Pertanyaan dasarnya adalah: dapatkah saya mengambil masalah di P dan menyelesaikannya menggunakan memori yang sangat, sangat sedikit?” Kata McKenzie.

Sebagian besar peneliti mencurigai jawabannya adalah tidak. Untuk membuktikannya, mereka perlu memilih masalah tertentu di P dan menunjukkan bahwa tidak mungkin untuk dipecahkan dengan trik penghematan memori yang cerdas.

Pada akhir 2000 -an, McKenzie dan ahli teori kompleksitas perintis Stephen Cook menyusun masalah yang tampak seperti kandidat yang menjanjikan. Disebut masalah evaluasi pohon, ini melibatkan berulang kali memecahkan masalah matematika yang lebih sederhana yang mengubah sepasang angka input menjadi satu output. Salinan masalah matematika ini diatur dalam lapisan seperti pertandingan di braket turnamen: output dari setiap lapisan menjadi input ke lapisan berikutnya sampai hanya ada satu output yang tersisa. Algoritma evaluasi pohon yang berbeda mewakili strategi yang berbeda untuk menghitung output akhir ini dari input awal – mereka mungkin melakukan perhitungan dalam urutan yang berbeda, atau mencatat hasil langkah -langkah perantara dengan cara yang berbeda.

Banyak algoritma dapat menyelesaikan masalah evaluasi pohon dengan cepat, meletakkannya di Kelas P. Tetapi setiap algoritma tersebut harus mencurahkan beberapa memori untuk angka -angka yang bekerja dengan, sementara juga menyimpan angka yang sudah dihitung untuk digunakan dalam langkah -langkah selanjutnya. Itu sebabnya Cook dan McKenzie curiga bahwa masalah itu tidak mungkin dipecahkan menggunakan memori terbatas. Mereka memformalkan intuisi ini di a Makalah 2010 Menulis bersama tiga peneliti lain, dan membuktikan bahwa setiap algoritma biasa untuk menyelesaikan masalah evaluasi pohon membutuhkan terlalu banyak memori untuk memenuhi syarat untuk keanggotaan di L.

Tetapi pekerjaan mereka tidak mengesampingkan kemungkinan algoritma aneh yang entah bagaimana dapat menggunakan memori yang sama untuk penyimpanan dan perhitungan secara bersamaan – komputasi yang setara dengan menggunakan halaman yang diisi dengan catatan penting sebagai kertas awal. Cook dan McKenzie berpikir algoritma aneh seperti itu tidak bisa ada, dan mereka cukup percaya diri untuk menaruh uang di atasnya: siapa pun yang bisa membuktikan bahwa mereka salah akan memenangkan $ 100 keren.

Konversi Katalitik

Michal Kouckýseorang ahli teori kompleksitas di Universitas Charles di Praha, belajar tentang hasil evaluasi pohon dari Cook selama cuti 2011 di Toronto. Dia menjadi bertekad untuk menyelesaikan apa yang telah dimulai Cook dan McKenzie, dengan membuktikan bahwa tidak ada cara untuk melakukan perhitungan tambahan menggunakan memori yang menyimpan data untuk nanti. Pencarian Koucký akan membawanya pada jalan memutar yang tidak terduga untuk penemuan komputasi katalitik. Hampir satu dekade kemudian, penemuan itu akan menginspirasi dua peneliti muda untuk kembali ke evaluasi pohon dan menyelesaikan taruhan Cook dan McKenzie untuk selamanya.

Tapi kembali ke kisah komputasi katalitik. Semuanya berawal ketika Koucký mengunjungi rekan -rekan di Amsterdam dan mengajukan pertanyaan yang telah menyibukkannya dalam istilah yang lebih sederhana: apa yang dapat Anda lakukan dengan memori yang sudah penuh?

“Tidak ada” adalah jawaban yang jelas. “Saya berpikir, ‘Oke, ini tentu saja sangat tidak berguna, dan kami akan membuktikannya,’” kata Harry Buhrmanpemimpin kelompok Amsterdam. “Dan kemudian kita tidak bisa membuktikannya.”

Terobosan datang beberapa bulan kemudian, ketika Buhrman mengunjungi kolaboratornya yang sering Richard Cleve di University of Waterloo. Mereka memutuskan untuk fokus pada skenario ekstrem, di mana memori penuh sangat besar. Jika komputer dengan sedikit memori bebas dapat mengakses memori penuh yang sangat besar ini, apakah itu memungkinkannya untuk menyelesaikan masalah yang tidak mungkin dengan memori bebas saja? Ini seperti pertanyaan “hard drive penuh dengan foto keluarga”, tetapi dengan hard drive ukuran pusat data.

Jika data tambahan itu tidak tersentuh – Anda tidak dapat berinteraksi sama sekali – maka itu pasti tidak membantu. Tetapi bagaimana jika Anda diizinkan untuk mengubah beberapa bit yang menyandikan data ini, selama Anda berjanji untuk mengatur ulang mereka setelah selesai? Anda tidak bisa begitu saja mencatat perubahan Anda, karena itu akan memakan lebih banyak ruang, jadi sebaliknya Anda harus memastikan bahwa perubahan Anda mudah dibalik. Terlebih lagi, Anda tidak bisa memilih konten data tambahan, jadi apa pun yang Anda lakukan harus bekerja untuk konfigurasi awal bit yang mungkin.

Itu adalah kendala yang cukup ketat, jadi tidak jelas bahwa memori ekstra bisa terbukti bermanfaat. Tetapi yang mengejutkan mereka, Buhrman dan Cleve menunjukkan bahwa jika Anda mengubah bit dengan cara yang benar, Anda benar -benar bisa mendapatkan semangat komputasi ekstra dari memori penuh.

“Itu sangat mengejutkan bagi semua orang,” kata Loff, yang merupakan mahasiswa pascasarjana dalam kelompok Buhrman pada saat itu, mengerjakan pertanyaan memori dengan sesama mahasiswa Speelman Florian. Tim segera memperluas hasilnya ke kelas masalah yang bahkan lebih besar, dan diterbitkan Hasil gabungan mereka pada 2014.

Mereka menamai komputasi katalitik kerangka kerja baru, meminjam istilah dari kimia. “Tanpa katalis, reaksinya tidak akan berlangsung,” kata Raghunath Tewariseorang ahli teori kompleksitas di Institut Teknologi India, Kanpur. “Tapi katalis itu sendiri tetap tidak berubah.”

Tidak jauh dari pohon

Sekelompok kecil peneliti terus mengembangkan komputasi katalitik lebih lanjut, tetapi tidak ada yang bahkan mencoba menerapkannya pada masalah evaluasi pohon yang awalnya menginspirasi pencarian Koucký. Untuk masalah itu, pertanyaan terbuka yang tersisa adalah apakah sejumlah kecil memori dapat digunakan untuk penyimpanan dan perhitungan secara bersamaan. Tetapi teknik komputasi katalitik bergantung pada memori ekstra dan penuh yang sangat besar. Kecilkan memori itu dan teknik tidak lagi berfungsi.

Namun, seorang peneliti muda tidak bisa tidak bertanya -tanya apakah ada cara untuk mengadaptasi teknik -teknik tersebut untuk menggunakan kembali memori dalam algoritma evaluasi pohon. Namanya James Cookdan baginya masalah evaluasi pohon adalah pribadi: Stephen Cook, ahli teori kompleksitas legendaris yang menciptakannya, adalah ayahnya. James bahkan telah mengerjakannya di sekolah pascasarjana, meskipun ia sebagian besar fokus subjek yang sama sekali tidak terkait. Pada saat ia menemukan makalah komputasi katalitik asli pada tahun 2014, James akan lulus dan meninggalkan Academia for Software Engineering. Tetapi bahkan ketika dia menyelesaikan pekerjaan barunya, dia terus berpikir tentang komputasi katalitik.

“Saya harus memahaminya dan melihat apa yang bisa dilakukan,” katanya.

Selama bertahun -tahun, James Cook bermain -main dengan pendekatan katalitik untuk masalah evaluasi pohon di waktu luangnya. Dia memberi ceramah tentang kemajuannya di simposium 2019 untuk menghormati ayahnya pekerjaan inovatif dalam teori kompleksitas. Setelah pembicaraan, ia didekati oleh seorang mahasiswa pascasarjana bernama Ian Mertzyang jatuh cinta dengan komputasi katalitik lima tahun sebelumnya setelah mempelajarinya sebagai sarjana muda yang mudah dipengaruhi.

“Itu seperti skenario pencetakan bayi burung,” kata Mertz.

Masak dan Mertz bergabung, dan upaya mereka segera membuahkan hasil. Pada tahun 2020, mereka merancang algoritma Itu memecahkan masalah evaluasi pohon dengan lebih sedikit memori daripada yang diperlukan minimum yang diperhitungkan oleh Cook Penatua dan McKenzie – meskipun hanya di bawah ambang batas itu. Namun, itu sudah cukup untuk mengumpulkan taruhan $ 100; Nyaman untuk para koki, setengahnya tetap di keluarga.

Tapi masih ada pekerjaan yang harus dilakukan. Para peneliti telah mulai mempelajari evaluasi pohon karena sepertinya pada akhirnya mungkin memberikan contoh masalah dalam P yang tidak ada dalam L – dengan kata lain, masalah yang relatif mudah yang tidak dapat diselesaikan dengan menggunakan memori yang sangat sedikit. Metode baru Cook dan Mertz menggunakan lebih sedikit memori daripada algoritma evaluasi pohon lainnya, tetapi masih digunakan secara signifikan lebih banyak daripada algoritma apa pun untuk masalah dalam evaluasi L. pohon turun, tetapi tidak keluar.

Pada tahun 2023, Cook dan Mertz keluar dengan algoritma yang ditingkatkan yang menggunakan lebih sedikit memori – lebih dari maksimum yang diizinkan untuk masalah pada L. Banyak peneliti sekarang curiga bahwa evaluasi pohon ada di L, dan bahwa bukti hanya masalah waktu. Para ahli teori kompleksitas mungkin memerlukan pendekatan yang berbeda untuk masalah P versus L.

Sementara itu, hasil Cook dan Mertz telah menggembleng minat dalam komputasi katalitik, dengan pekerjaan baru menjelajahi koneksi ke keacakan dan efek dari memungkinkan a sedikit kesalahan dalam mengatur ulang memori penuh ke keadaan aslinya.

“Kami belum selesai mengeksplorasi apa yang bisa kami lakukan dengan teknik -teknik baru ini,” kata McKenzie. “Kita bisa mengharapkan lebih banyak kejutan.”

Cerita asli dicetak ulang dengan izin dari Berapa banyak majalah, publikasi editorial independen dari Yayasan Simons yang misinya adalah untuk meningkatkan pemahaman publik tentang sains dengan meliput perkembangan penelitian dan tren matematika dan ilmu fisik dan kehidupan.