Hasil klasik itu merupakan cara untuk mengubah algoritme apa pun dengan anggaran waktu tertentu menjadi algoritme baru dengan anggaran ruang yang sedikit lebih kecil. Williams melihat bahwa simulasi berbasis kerikil lunak akan membuat penggunaan ruang algoritme baru jauh lebih kecil—kira-kira setara dengan akar kuadrat dari anggaran waktu algoritme asli. Algoritme yang hemat ruang itu juga akan jauh lebih lambat, jadi simulasi tersebut tidak mungkin memiliki aplikasi praktis. Namun dari sudut pandang teoretis, ini sungguh revolusioner.
Selama 50 tahun, para peneliti mengira mustahil untuk memperbaiki simulasi universal Hopcroft, Paul, dan Valiant. Gagasan Williams—jika berhasil—tidak hanya akan memecahkan rekor mereka, tapi menghancurkannya.
"Aku memikirkannya, dan seperti, ‘Yah, itu tidak mungkin benar,’" kata Williams. Ia mengesampingkannya dan tidak kembali hingga hari naas di bulan Juli itu, saat ia mencoba menemukan kelemahan argumen tersebut dan gagal. Setelah menyadari tidak ada kelemahan, ia menghabiskan berbulan-bulan menulis dan menulis ulang pembuktian agar sejelas mungkin.
Akhir Februari, Williams akhirnya mempublikasikan makalah selesai secara daring. Cook dan Mertz sama terkejutnya dengan yang lain. "Aku harus jalan-jalan dulu sebelum melakukan apa pun," kata Mertz.
Valiant mendapat pratinjau hasil Williams yang meningkatkan temuannya puluhan tahun lalu selama perjalanan pagi. Bertahun-tahun ia mengajar di Harvard University, tak jauh dari kantor Williams di MIT. Mereka pernah bertemu, tapi tidak tahu tinggal di lingkungan yang sama hingga berpapasan di bus di hari bersalju Februari, beberapa minggu sebelum hasil itu publik. Williams menjelaskan pembuktiannya pada Valiant yang terkejut dan berjanji mengirimkan makalahnya.
"Aku sangat, sangat terkesan," kata Valiant. "Jika kamu mendapatkan hasil matematika terbaik dalam 50 tahun, pasti kamu melakukan sesuatu yang benar."
PSPACE: Batas Akhir
Dengan simulasi barunya, Williams membuktikan hasil positif tentang kekuatan komputasi ruang: Algoritme yang menggunakan ruang relatif sedikit dapat menyelesaikan semua masalah yang membutuhkan waktu sedikit lebih banyak. Lalu, dengan beberapa baris matematika, ia membalikkannya dan membuktikan hasil negatif tentang kekuatan komputasi waktu: Setidaknya beberapa masalah tak bisa diselesaikan kecuali menggunakan waktu lebih banyak daripada ruang. Hasil kedua yang lebih sempit itu sesuai dengan harapan peneliti. Yang aneh adalah cara Williams mencapainya, dengan pertama membuktikan hasil yang berlaku untuk semua algoritme, apapun masalah yang diselesaikannya.
"Aku masih sulit mempercayainya," kata Williams. "Terlalu bagus untuk jadi kenyataan."
Williams menggunakan teknik Cook dan Mertz untuk membangun hubungan lebih kuat antara ruang dan waktu—kemajuan pertama dalam 50 tahun.
Secara kualitatif, hasil kedua Williams mungkin terdengar seperti solusi lama yang dicari untuk masalah P versus PSPACE. Perbedaannya terletak pada skala. P dan PSPACE adalah kelas kompleksitas yang sangat luas, sementara hasil Williams bekerja pada tingkat lebih rinci. Ia menetapkan kesenjangan kuantitatif antara kekuatan ruang dan waktu, dan untuk membuktikan PSPACE lebih besar dari P, peneliti harus membuat kesenjangan itu jauh, jauh lebih lebar.
Itu tantangan menakutkan, seperti membuka retakan trotoar dengan linggis hingga selebar Grand Canyon. Tapi mungkin bisa dicapai dengan versi modifikasi prosedur simulasi Williams yang mengulang langkah kunci berkali-kali, menghemat sedikit ruang setiap kali. Ini seperti cara berulang memperpanjang linggis—buat cukup besar, dan kamu bisa membuka apa saja. Peningkatan berulang itu tidak bekerja dengan versi algoritme saat ini, tapi peneliti tidak tahu apakah itu batasan mendasar.
"Mungkin hambatan terakhir, atau hambatan 50 tahun," kata Valiant. "Atau mungkin sesuatu yang bisa diselesaikan minggu depan."
Jika masalah itu selesai minggu depan, Williams akan menyesal. Sebelum menulis makalah, ia berbulan-bulan mencoba dan gagal memperluas hasilnya. Tapi bahkan jika perluasan itu tidak mungkin, Williams yakin eksplorasi ruang lebih lanjut akan mengarah pada sesuatu yang menarik—mungkin kemajuan pada masalah yang sama sekali berbeda.
"Aku tak pernah bisa membuktikan persis apa yang ingin kubuktikan," katanya. "Tapi seringkali, yang kubuktikan jauh lebih baik dari yang kuinginkan."
Catatan editor: Scott Aaronson adalah anggota dewan penasihat Quanta Magazine.
Artikel asli dicetak ulang dengan izin dari Quanta Magazine, publikasi independen editorial dari Simons Foundation yang misinya meningkatkan pemahaman publik tentang sains dengan meliput perkembangan dan tren penelitian dalam matematika serta ilmu fisika dan kehidupan.