Ryan Williams Membuktikan Memori Komputer Lebih Kuat Dari Waktu Dalam Teori Kompleksitas

Ryan Williams, seorang ilmuwan komputer dari MIT, menemukan bukti matematis bahwa memori dalam komputer lebih kuat daripada yang selama ini diyakini. Selama 50 tahun, para ilmuwan sulit membuktikan hubungan tepat antara waktu dan ruang dalam komputer, tetapi Williams berhasil memperbaiki metode yang memungkinkan algoritma menggunakan jauh lebih sedikit memori.Keberhasilan Williams lahir dari pengaruh dan ide yang telah dikembangkan selama beberapa dekade oleh para ilmuwan terkenal seperti Juris Hartmanis, John Hopcroft, Wolfgang Paul, dan Leslie Valiant. Mereka sebelumnya menciptakan simulasi yang bisa menghemat ruang memori, namun belum ada yang mampu mengalahkan batasan tersebut sampai sekarang.Salah satu kunci terobosan Williams adalah memanfaatkan ide baru dari Stephen Cook dan Ian Mertz yang memungkinkan tumpang tindih penyimpanan data dalam memori. Dengan metode ini, Williams menciptakan simulasi universal yang lebih efisien, sehingga algoritma bisa menggunakan ruang memori sekitar akar kuadrat dari waktu yang dibutuhkan sebelumnya.Meski simulasi ini membuat algoritma menjadi jauh lebih lambat, hasil ini sangat penting secara teori karena membuka kemungkinan untuk membuktikan teorema lama yang selama ini sulit diselesaikan, termasuk membuktikan perbedaan antara kelas kompleksitas komputer P dan PSPACE.Para ahli seperti Avi Wigderson, Paul Beame, dan Leslie Valiant sangat mengapresiasi hasil Williams, menyebutnya sebagai kemajuan besar dan suatu hari bisa memecahkan tantangan besar dalam ilmu komputer. Williams sendiri merasa hasil ini terlalu bagus untuk dipercaya dan berharap bisa membuka jalan penelitian baru.