Courtesy of Wired

Penemuan Ryan Williams Buktikan Memori Komputer Lebih Kuat dari Waktu Komputasi

Membuktikan hubungan matematis baru antara ruang memori dan waktu komputasi yang menunjukkan ruang memori lebih kuat daripada waktu dalam komputasi dan menghasilkan simulasi universal yang lebih efisien dari sebelumnya.

13 Jul 2025, 18.00 WIB

40 dibaca

Ikhtisar 15 Detik

Penelitian Ryan Williams menunjukkan bahwa memori memiliki kekuatan yang lebih besar dalam komputasi daripada yang sebelumnya diperkirakan.
Bukti matematis yang dihasilkan dapat mengubah cara kita memahami hubungan antara waktu dan ruang dalam algoritma.
Hasil ini membuka jalan bagi penelitian lebih lanjut dalam teori kompleksitas, khususnya dalam menjawab masalah P vs PSPACE.

Cambridge, United States - Ryan Williams, ilmuwan komputer dari MIT, telah mengubah pandangan tentang keterkaitan ruang memori dan waktu komputasi yang sudah dipercaya selama puluhan tahun. Ia menemukan cara baru untuk mengubah algoritma agar menggunakan ruang memori jauh lebih sedikit tanpa mengubah fungsinya, meskipun waktu yang dibutuhkan jadi lebih lama. Penemuan ini adalah sebuah revolusi dalam teori kompleksitas.

Sejak masa kuliahnya di Cornell, Williams sangat tertarik dengan teori kompleksitas dan kelas masalah komputasi yang membagi masalah berdasarkan sumber daya yang dibutuhkan, yaitu waktu dan ruang. Mentor utamanya adalah Juris Hartmanis, yang pertama kali mendefinisikan kelas-kelas ini secara formal. Selama bertahun-tahun, masalah hubungan antara kelas waktu dan ruang menjadi tantangan besar di bidang ini.

Sebuah metode lama yang dibuat Hopcroft, Paul, dan Valiant pada tahun 1975 memberikan simulasi universal yang sedikit mengurangi penggunaan ruang dengan biaya waktu lebih banyak. Namun, batasan kuat dari Wolfgang Paul membuat ilmuwan lain merasa bahwa tidak mungkin memperbaiki simulasi ini. Tetapi sebuah temuan dari Cook dan Mertz tahun 2023 yang mengizinkan data 'ditumpuk' di ruang memori membuka jalan baru.

Williams menggunakan ide tersebut untuk membuat simulasi baru yang mengurangi ruang memori yang diperlukan hingga kira-kira akar kuadrat dari waktu komputasi asli. Ini merupakan peningkatan drastis yang membuka kemungkinan bukti baru dalam teori kompleksitas, khususnya terkait kelas P dan PSPACE yang telah lama menjadi teka-teki.

Temuan ini meskipun teoretis dan belum tentu praktis untuk aplikasi langsung, memiliki potensi memberikan kemajuan signifikan dan membuka jalan menuju pemecahan masalah utama di komputer sains. Para pakar di bidangnya menyambut dengan sangat antusias dan yakin bahwa ini langkah besar dalam pengetahuan tentang sumber daya komputasi.

Sumber: https://wired.com/story/for-algorithms-a-little-memory-outweighs-a-lot-of-time/

Pertanyaan Terkait

Apa yang ditemukan Ryan Williams tentang hubungan antara memori dan waktu dalam komputasi?

Ryan Williams menemukan bahwa memori dapat menjadi lebih kuat dari yang diperkirakan dalam komputasi, menunjukkan bahwa sedikit memori bisa sebanding dengan banyak waktu.

Mengapa bukti matematis Williams dianggap penting dalam teori kompleksitas?

Bukti matematis Williams dianggap penting karena memberikan prosedur umum untuk mengubah algoritma sehingga menggunakan lebih sedikit ruang, serta membuktikan beberapa masalah tidak dapat diselesaikan dalam waktu terbatas.

Siapa saja tokoh penting yang terlibat dalam artikel ini?

Tokoh penting dalam artikel ini termasuk Ryan Williams, Avi Wigderson, Stephen Cook, dan Juris Hartmanis.

Apa yang dimaksud dengan kelas kompleksitas P dan PSPACE?

Kelas kompleksitas P mencakup masalah yang dapat diselesaikan dalam waktu yang wajar, sedangkan PSPACE mencakup masalah yang dapat diselesaikan dengan penggunaan ruang terbatas.

Apa dampak dari hasil penelitian Ryan Williams terhadap pemahaman tentang algoritma?

Hasil penelitian Ryan Williams memberikan wawasan baru tentang trade-off antara waktu dan ruang dalam komputasi, serta membuka jalan untuk penelitian lebih lanjut dalam teori kompleksitas.