Cakrawala Baru Riset Algoritme, Bukti bahwa “Sedikit Memori Bisa Lebih Kuat daripada Banyak Waktu”

• Bukti baru yang dipublikasikan oleh teoretikus ilmu komputer MIT Ryan Williams menunjukkan bahwa sumber daya memori bisa menjadi sumber daya komputasi yang lebih kuat daripada waktu
• Memecahkan kemandekan selama 50 tahun terkait hubungan kompleksitas waktu-ruang, dan menyajikan cara untuk mengubah semua algoritme agar dapat menggunakan memori yang lebih sedikit
• Inti pembuktian ini adalah gagasan untuk menggeneralisasi simulasi hemat ruang, sehingga penggunaan ruang algoritme dapat dikurangi hingga tingkat akar kuadrat dari waktu
• Hal ini menghasilkan kemajuan dalam membuktikan secara kuantitatif perbedaan antara kelas PSPACE dan P, serta membuka kemungkinan menuju pembuktian kesenjangan yang lebih lebar
• Para ahli menilai pencapaian ini sebagai “kemajuan yang menakjubkan sekaligus titik awal eksplorasi baru”, dan hasil ini berpotensi menjadi petunjuk untuk memecahkan problem sulit lain dalam ilmu komputer teoretis

---

One Small Step for Space, One Giant Leap for Complexity

Ringkasan bukti baru Ryan Williams

• Pada musim panas 2024, Ryan Williams dari MIT sedang meninjau pembuktiannya ketika ia menyadari bahwa ide yang semula ia kira sebagai kesalahan ternyata benar-benar valid
• Ia mengusulkan prosedur umum untuk mengubah semua algoritme agar dapat dijalankan dengan memori yang lebih sedikit
• Dari sini, ia dapat membuktikan bahwa beberapa persoalan tidak dapat diselesaikan dalam batasan waktu tertentu

Waktu dan ruang: dua sumber daya komputasi

• Semua algoritme menggunakan waktu dan memori (ruang)
• Sebelumnya, diyakini bahwa dalam menyelesaikan persoalan tertentu, ruang berbanding lurus dengan waktu
• Bukti Williams menetapkan secara matematis bahwa ruang bisa lebih kuat daripada waktu

Awal mula dan sejarah ilmu komputer teoretis

• Juris Hartmanis dan Richard Stearns membangun definisi kompleksitas waktu/ruang pada 1960-an
• Mereka meletakkan dasar untuk mengelompokkan persoalan ke dalam kelas kompleksitas berdasarkan sumber daya yang diperlukan untuk menyelesaikannya
• P adalah persoalan yang bisa diselesaikan dalam waktu yang masuk akal, sedangkan PSPACE adalah persoalan yang bisa diselesaikan dengan memori yang memadai

Kemajuan pertama: teknik simulasi tahun 1975

• Hopcroft, Paul, Valiant mengembangkan prosedur simulasi universal yang mengubah semua algoritme agar memakai ruang yang sedikit lebih kecil
• Ini menjadi langkah awal untuk menjelaskan keterkaitan waktu dan ruang, tetapi kemudian menemui batas
• Karena asumsi bahwa data tidak dapat menempati ruang yang sama pada saat yang bersamaan, kemajuan lebih lanjut dianggap mustahil

Titik balik: Squishy Pebbles

• Pada 2010, teoretikus kompleksitas perintis Stephen Cook dan rekan-rekannya merancang persoalan evaluasi pohon - Pebbles and Branching Programs for Tree Evaluation, lalu membuktikan bahwa tugas ini tidak mungkin bagi algoritme dengan anggaran ruang di bawah ambang tertentu
  • Namun ada celah. Pembuktian tersebut didasarkan pada asumsi yang sama yang secara intuitif digunakan Paul dan rekan-rekannya beberapa dekade sebelumnya
  • Yakni, algoritme tidak dapat menyimpan data baru di ruang yang sudah penuh
  • Selama lebih dari 10 tahun, para teoretikus kompleksitas berupaya menutup celah itu
• James Cook, putra Stephen Cook, dan Ian Mertz pada 2023 memublikasikan algoritme persoalan evaluasi pohon yang mematahkan asumsi lama tersebut: Tree Evaluation Is in Space 𝑂 (log 𝑛 · log log 𝑛)
• Mereka mengusulkan model representasi baru di mana data di dalam memori dapat saling bertumpang tindih secara fisik
• Pendekatan ini menjadi kunci untuk melampaui batas simulasi lama

Lompatan penentu dari Williams

• Setelah melihat presentasi para mahasiswa dan mengenal teknik Cook-Mertz, Williams mendapatkan ide untuk menerapkannya pada simulasi universal
• Simulasi baru ini dapat mengurangi kebutuhan ruang algoritme hingga ke tingkat akar kuadrat dari waktu
• Pada Februari 2025 ia memublikasikan makalah finalnya di arXiv, dan mendapat pujian luas dari kalangan akademik

Makna dari hasil ini

• Bukti ini tidak secara langsung membuktikan bahwa PSPACE > P, tetapi merupakan terobosan penting yang membuka ‘celah’ ke arah itu
• Jika prosedur ini kelak dapat diterapkan berulang kali untuk menciptakan kesenjangan yang lebih besar, maka penyelesaian masalah P vs PSPACE bisa semakin dekat
• Ini dapat menjadi petunjuk awal untuk memecahkan salah satu problem tertua dalam ilmu komputer

Penutup yang membekas

• Williams mengenang hasil ini dengan mengatakan:
  “Saya memang tidak berhasil membuktikan hal yang benar-benar ingin saya buktikan, tetapi yang akhirnya saya buktikan justru lebih baik daripada yang saya inginkan.”

[nunojay]

....Eh?

[GN⁺]

Komentar Hacker News

• Tanpa membahas faktor fuzz, mesin Turing multi-tape yang berjalan dalam waktu t dapat disimulasikan dengan ruang O(sqrt(t log t)) (biasanya waktu eksekusinya menjadi lebih lama dari t) Simulating Time With Square-Root Space
  • Disayangkan artikel Quanta sering mencampurkan terlalu banyak ungkapan puitis atau berlebihan ke dalam matematika sehingga menimbulkan salah paham. Artikel Quanta mengatakan “tugas-tugas tertentu memerlukan ruang sebesar waktu eksekusinya”, tetapi bahkan hanya dengan melihat hierarchy kompleksitas, intuisi umum seperti itu tidak otomatis muncul. Tidak tepat membangun intuisi keseluruhan hanya dari cerita tentang “sebagian algoritme”.
  • Mungkin karena terlalu ingin ramah pada pembaca, Quanta menjelaskan kelas kompleksitas P hanya sebagai “semua masalah yang bisa diselesaikan dalam waktu yang masuk akal” tanpa menyebut istilah polynomial sama sekali, dan itu terasa agak merendahkan.
• Dalam “Camel Book” yang memuat filosofi Perl, ada kutipan seperti ini: “Jika kekurangan memori, Anda bisa membelinya, tetapi jika kekurangan waktu, tidak ada yang bisa dilakukan.” Saya menyukai buku itu karena memang lucu.
  • Menurut saya kalimat itu juga punya dua sisi. Program yang membutuhkan memori lebih besar daripada yang tersedia di komputer tidak bisa dijalankan saat itu juga, sedangkan sesuatu yang memakan waktu lama tetap setidaknya bisa dijalankan, jadi waktu tetap merupakan sumber daya yang penting.
• Kemenangan lookup table yang menyimpan nilai-nilai pra-hitung. Dulu saya pernah merasa bahwa kalau semua komputasi bisa disimpan secara terpusat sampai prosesor nyaris tak diperlukan, kecepatan pemrosesan bisa berubah drastis. (Tentu ada tantangan besar lain berupa pencarian cepat.)
  • Saat dulu mulai bekerja di sistem penyimpanan, saya pernah mengusulkan ide untuk menghitung dan menyimpan semua blok 4KB terlebih dahulu, lalu terkejut ketika diberi tahu bahwa jumlah blok 4KB unik lebih banyak daripada jumlah atom di alam semesta.
  • Algoritme HashLife melakukan sesuatu yang mirip dan Turing-complete pada Conway’s Game of Life. Saya merasa menakjubkan bahwa bahkan saat menghadapi keadaan yang sangat kompleks dan beragam, kita tetap bisa melompat jauh dengan menghitung lebih dulu keadaan masa depan.
  • Candaan bahwa tidak ada masalah dengan ide untuk me-cache lookup retrieval itu sendiri.
  • Ini pada dasarnya sudah diwujudkan lewat caching tingkat komunitas, yaitu distribusi perangkat lunak yang sudah dipra-kompilasi. Hambatan tradisional bahwa kita harus mengorbankan fitur bahasa karena tidak bisa mengompilasi secara efisien dapat diatasi dengan kompilasi paralel di cloud dan cache global. Jika cukup dikompilasi sekali saat rilis, semua orang bisa memakainya bersama-sama.
  • Sebagai perpanjangan dari gagasan “jika semua komputasi disimpan di pusat, prosesor mungkin tidak dibutuhkan”, saya bahkan terpikir untuk mememoisasi riwayat pencarian itu sendiri.
• Karena gaya Quanta yang puitis, sulit memahami apakah riset ini benar-benar bisa diterapkan pada komputer nyata atau hanya skenario teoretis murni. Saya penasaran apakah maksudnya komputer akan menjadi lebih lambat sebagai imbalan karena menggunakan lebih banyak memori.
• Saya sudah lama menekuni pemrograman grafis raster, jadi penggunaan lookup table terasa sangat alami bagi saya. Belakangan ini saya membuat alat server yang menyimpan berbagai bentuk lebih dulu di DB agar hasil yang sudah dioptimalkan bisa digunakan setiap kali ada query. Polanya tidak rumit dan intuitif. Saya tidak pernah belajar khusus dari profesor MIT atau semacamnya, itu hanya cara kerja yang saya kuasai lewat praktik, jadi rasanya menyenangkan melihat ada bukti matematis yang membenarkannya. Banyak pengetahuan algoritmik memang kadang lahir dari pengalaman para praktisi. (misalnya: algoritme winding number)
  • Hasil optimisasi game yang saya dapat akhir-akhir ini semuanya berasal dari cara menangani lookup table sesuai konteks. Lookup table tidak harus selalu berupa array statis; data yang berubah sedikit seiring waktu juga bisa dimanfaatkan dengan cara yang sama. Saya jadi terbuka pada pendekatan memindahkan pekerjaan ke GPU, dan ada efisiensi besar dalam struktur yang mengubah hanya sebagian tabel saat runtime lalu mengirimkannya ke GPU seperti tekstur, alih-alih tabel yang dibuat statis saat kompilasi atau runtime. Batas tentang apa yang bisa disebut lookup table menjadi kabur.
• Secara intuitif terasa masuk akal bahwa ruang (memori) bisa merepresentasikan hasil yang jauh lebih banyak daripada waktu. Pada tape biner sepanjang n, Anda bisa menulis selama O(n) waktu, tetapi ada 2^n kemungkinan konfigurasi untuk tape sepanjang n. Jika ruang digunakan dengan baik, daya representasinya bisa jauh melampaui waktu.
  • Intuisi saya: satu sel bisa menyimpan hasil antara dari ratusan langkah perhitungan. Jika hasil antara itu tidak bisa disimpan dan kita harus menghitung ulang hal yang sama setiap saat, efisiensinya akan turun besar. Situasi dengan cache hit rate 0% sangat jarang; biasanya efisiensi bisa ditingkatkan dengan memanfaatkan ruang. Sebaliknya, sulit bagi satu unit waktu untuk menggantikan ruang ratusan sel, dan dalam arsitektur komputasi saat ini SIMD tak terbatas tidak mungkin.
  • Asumsi akses acak memori O(1) terlalu sering dianggap wajar, padahal pada kenyataannya biaya akses bisa meningkat hingga O(n^(1/3)) seiring membesarnya ukuran komputer. Ini sangat terasa di data center. Seingat saya modelnya bukan UMA.
  • Karena P ≠ PSPACE belum terbukti, ini adalah ranah yang secara matematis lebih sulit dibuktikan daripada sekadar mengandalkan intuisi.
  • Di sisi lain, itu memang benar, tetapi untuk masalah yang sulit diparalelkan (misalnya: alternating machine PTIME=PSPACE), ruang mungkin tidak memberi keuntungan sebesar itu. Dalam makalah ini lompatan dari t/log t ke sqrt(t log t) memang revolusioner, tetapi pasti ada batas substantif yang tidak bisa ditembus bahkan dengan paralelisasi tak terbatas.
  • Dalam praktik, hal ini bergantung pada sifat pekerjaannya. Jika akses ke penyimpanan jauh lebih lambat daripada operasi assignment, menghitung ulang kadang justru lebih cepat.
• “Hubungan timbal balik” antara waktu dan ruang bisa dijelaskan sebagai fenomena bahwa ketika satu sumber daya dibatasi, nilai optimal sumber daya lain tidak otomatis bisa diperoleh. Misalnya pada algoritme pengurutan, ketika ada tiga batasan waktu/ruang/stabilitas, jika kita juga menuntut stabilitas maka efisiensi waktu atau ruang justru bisa menurun. Sampai sekarang belum ada stable sort yang secepat dan sehemat memori seperti non-stable sort.
• Secara pribadi saya menyukai gaya artikel Quanta Magazine. Bukan hanya untuk ilmuwan komputer, tetapi juga memperluas wawasan orang awam yang tertarik pada bidang terkait. Sudut pandang menyeluruh dan gaya penjelasannya yang akrab sering menjadi pemicu perspektif dan ide baru.
• Membagikan tautan ke presentasi dan makalah Ryan Williams.
• Jika mesin Turing single-tape menerima bilangan biner N sebagai input lalu ingin menulis 1 sebanyak N kali di sisi kanan tape, tampaknya ia memerlukan ruang N dalam waktu N. Jadi saya penasaran bagaimana ini bisa disimulasikan dengan ruang yang lebih kecil dari N. Mengingat sifat struktur mesin Turing yang tidak bisa melompat ke posisi sembarang pada tape, saya juga penasaran apa hubungannya dengan komputer nyata.
  • Mesin Turing multi-tape jauh lebih cepat daripada single-tape, dan “ruang” yang dimaksud di sini adalah ruang kerja sementara di luar input/output.
  • Makalahnya terutama menargetkan masalah keputusan, jadi hanya mempertimbangkan situasi ketika output yang dibutuhkan hanya 1 bit. Jika outputnya N bit, penjelasannya adalah bahwa itu pada dasarnya setara dengan menggabungkan N masalah keputusan.