CAKRAM PENUH PINJAMAN MEMBUAT KOMPUTER LEBIH CEPAT

Sebagian masalah murah dalam waktu tetapi rakus memori, sebagian lagi sebaliknya. Untuk beberapa tugas dasar, para ahli teori telah membuktikan batas tegas bagi tawar-menawar ini: dengan memori kerja yang kecil, Anda tidak bisa cepat. Sebuah makalah baru menunjukkan bahwa sumber daya yang aneh, yaitu memori yang sudah penuh dan harus dikembalikan utuh, mematahkan batas-batas itu.

Hard disk pinjaman

Model ini disebut komputasi katalitik (catalytic computing), diperkenalkan pada 2014 oleh Buhrman, Cleve, Koucký, Loff, dan Speelman. Sebuah algoritma mendapat memori bersih yang sangat kecil, sekitar log n bit untuk masukan berukuran n, ditambah memori kotor yang sangat besar dan sudah terisi data sembarang yang tidak dipilihnya. Algoritma boleh memakai keduanya sesuka hati, tetapi ketika berhenti, setiap bit memori kotor harus persis seperti semula.

Para penulis memakai gambaran yang lazim: Anda meminjam hard disk raksasa milik teman, penuh kenangan digital berharga, untuk menjalankan suatu komputasi. Anda tidak ingin kehilangan teman, jadi Anda mengembalikan setiap bit setelah selesai.

Awalnya model ini dimaksudkan untuk membuktikan bahwa memori semacam itu tidak berguna. Secara intuitif, untuk memulihkan semuanya Anda harus menyimpan seluruh informasi, sehingga tidak pernah ada ruang yang terbebas. Mengejutkannya, yang terjadi justru sebaliknya: memori penuh memungkinkan penyelesaian masalah yang tidak diketahui caranya dengan memori bersih saja. Tetapi hasil-hasil itu menyangkut ruang, dan algoritmanya sangat lambat.

Lebih cepat daripada yang terbukti mungkin

Adelmo Morrison Orozco, Nathan Sheffield, dan Ryan Williams (MIT) kini meninjau kecepatan. Dengan memori bersih logaritmik dan memori pinjaman berukuran polinomial, mereka memberikan algoritma yang:

• mengurutkan daftar dan menghitung transformasi Fourier diskret dalam waktu n^(1+o(1)), hampir linear;
• mengalikan matriks dalam waktu n^(ω+o(1)), secepat metode terbaik yang diketahui dengan memori tak terbatas.

Tanpa cakram pinjaman, sudah terbukti bahwa hasil kali waktu dan memori harus setidaknya berorde n² untuk pengurutan dan transformasi Fourier, dan n³ untuk perkalian matriks. Jadi algoritma katalitik ini mencapai kecepatan yang tidak dapat dicapai algoritma bermemori kecil biasa mana pun. Para penulis menyebutnya demonstrasi tanpa syarat pertama bahwa algoritma katalitik mengungguli padanan non-katalitiknya.

Ubah, baca, batalkan

Bahan kuncinya adalah trik kombinatorika yang singkat. Misalkan sebuah algoritma dapat mengubah satu bagian memori pinjaman bolak-balik antara nilai tak diketahui τ dan τ + x, dengan x adalah hasil yang ingin diketahuinya. Dalam sebuah tabel “pembantu” besar, yang juga dipinjam, tambahkan 1 pada sekumpulan entri yang dipilih dengan cermat. Entri di posisi τ bertambah satu jika dan hanya jika x termasuk dalam himpunan tertentu. Lalu jalankan setiap langkah secara mundur, dan cakram kembali seperti semula, kecuali sepotong jawaban yang Anda inginkan.

Dengan menumpuk trik ini lapis demi lapis, rangkaian dangkal dapat dievaluasi dengan cepat. Para penulis kemudian merumuskan ulang jaringan pengurutan, transformasi Fourier cepat, dan perkalian matriks cepat sebagai rangkaian semacam itu. Untuk aritmetika, hanya lapisan yang mengalikan dua besaran tak diketahui yang memakan biaya tambahan; lapisan yang murni linear hampir gratis.

Perbandingan yang adil

Satu keberatan: batas-batas klasik mengasumsikan jawaban ditulis sekali, dari kiri ke kanan, pada pita keluaran terpisah, sedangkan algoritma katalitik menulis jawabannya ke dalam cakram pinjaman. Makalah ini menjawabnya. Para penulis menunjukkan bahwa algoritma mereka dapat menulis jawaban dalam dua kali lintasan pada pita keluaran, dan bahwa bagi algoritma biasa, dua lintasan tidak lebih membantu daripada satu. Jadi batas-batas itu tetap berlaku, dan pemisahannya tetap sah. Mereka juga membuktikan bahwa satu lintasan tidak cukup bahkan dengan cakram pinjaman: pengurutan lalu menabrak penghalang n² yang sama.

Daftar panjang penerima manfaat

Alat yang sama menghasilkan algoritma katalitik cepat untuk mengalikan bilangan bulat besar dan polinomial, menghitung segitiga dan menemukan klik dalam jaringan, mendeteksi lintasan dan siklus, serta mencocokkan pola teks dengan karakter wildcard. Waktu jalannya menyamai, hingga faktor kecil, algoritma terbaik yang diketahui yang memiliki memori sebanyak yang diinginkan. Dalam setiap kasus, memori pinjaman tetap harus kembali persis seperti saat dipinjamkan.