Penemuan Ryan Williams Buktikan Memori Komputer Lebih Kuat dari Waktu Komputasi

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.