Untuk algoritma, memori adalah sumber daya yang jauh lebih kuat daripada waktu

Versi aslinya dari cerita ini muncul di Berapa banyak majalah.

Suatu sore Juli di tahun 2024, Ryan Williams Berangkat untuk membuktikan dirinya salah. Dua bulan telah berlalu sejak dia mencapai penemuan mengejutkan tentang hubungan antara waktu dan memori dalam komputasi. Itu adalah sketsa kasar dari bukti matematis bahwa memori lebih kuat daripada yang diyakini oleh para ilmuwan komputer: sejumlah kecil akan sama bermanfaatnya dengan banyak waktu dalam semua perhitungan yang mungkin. Kedengarannya sangat mustahil sehingga dia menganggap sesuatu harus salah, dan dia segera mengesampingkan bukti untuk fokus pada ide -ide yang kurang gila. Sekarang, dia akhirnya mengukir waktu untuk menemukan kesalahan.

Bukan itu yang terjadi. Setelah berjam -jam meneliti argumennya, Williams tidak dapat menemukan satu kelemahan pun.

“Saya hanya berpikir saya kehilangan akal,” kata Williams, seorang ilmuwan komputer teoretis di Massachusetts Institute of Technology. Untuk pertama kalinya, ia mulai menghibur kemungkinan bahwa mungkin, mungkin saja, ingatan benar -benar sekuat pekerjaannya.

Selama bulan -bulan berikutnya, ia menyempurnakan detailnya, meneliti setiap langkah, dan meminta umpan balik dari beberapa peneliti lain. Pada bulan Februari, akhirnya dia memposting buktinya secara onlineuntuk meluasnya pujian.

“Luar biasa. Sangat indah,” kata Avi Wigdersonseorang ilmuwan komputer teoretis di Institute for Advanced Study di Princeton, New Jersey. Begitu dia mendengar berita itu, Wigderson mengirimi Williams email ucapan selamat. Baris subjeknya: “Kamu mengejutkan pikiranku.”

Waktu dan memori (juga disebut ruang) adalah dua sumber daya paling mendasar dalam perhitungan: setiap algoritma membutuhkan waktu untuk menjalankan dan membutuhkan ruang untuk menyimpan data saat berjalan. Sampai sekarang, satu -satunya algoritma yang diketahui untuk menyelesaikan tugas -tugas tertentu membutuhkan sejumlah ruang yang kira -kira sebanding dengan waktu berjalan mereka, dan para peneliti telah lama menganggap tidak ada cara untuk melakukan yang lebih baik. Bukti Williams menetapkan prosedur matematika untuk mengubah algoritma apa pun – tidak peduli apa yang dilakukannya – ke dalam bentuk yang menggunakan ruang yang jauh lebih sedikit.

Terlebih lagi, hasil ini – sebuah pernyataan tentang apa yang dapat Anda hitung mengingat sejumlah ruang – juga menyiratkan hasil kedua, tentang apa yang tidak dapat Anda hitung dalam jumlah waktu tertentu. Hasil kedua ini tidak mengejutkan dalam dirinya sendiri: para peneliti mengharapkan itu benar, tetapi mereka tidak tahu bagaimana membuktikannya. Solusi Williams, berdasarkan hasil pertama yang menyapu, terasa hampir berlebihan, mirip dengan membuktikan bahwa seorang pembunuh yang dicurigai bersalah dengan membangun alibi besi untuk semua orang di planet ini. Ini juga bisa menawarkan cara baru untuk menyerang salah satu masalah terbuka tertua dalam ilmu komputer.

“Ini hasil yang sangat menakjubkan, dan kemajuan besar -besaran,” kata Paul Beameseorang ilmuwan komputer di University of Washington. “Ini sedikit kurang mengejutkan bahwa Ryan melakukan ini.”

Ruang untuk berkeliaran

Williams, 46, memiliki wajah yang terbuka dan ekspresif dan sedikit abu -abu di rambutnya. Kantornya, yang menghadap ke menara berwarna -warni dari MIT’s Stata Center, adalah ilustrasi lain tentang penggunaan ruang kreatif. Sepasang tikar yoga telah mengubah langkan jendela menjadi sudut pembacaan darurat, dan meja terselip menjadi sudut berbentuk aneh, membebaskan ruang untuk sofa yang menghadap papan tulis besar penuh dengan coretan matematika.

MIT jauh dari rumah masa kecil Williams di pedesaan Alabama, di mana tidak ada kekurangan ruang. Dia tumbuh di pertanian seluas 50 hektar dan pertama kali melihat komputer pada usia 7, ketika ibunya mengantarnya melintasi county untuk kelas pengayaan akademik khusus. Dia ingat telah diakui oleh program sederhana untuk menghasilkan tampilan kembang api digital.

“Itu mengambil warna acak dan mengirimkannya ke arah acak dari tengah monitor,” kata Williams. “Kamu tidak bisa meramalkan gambar apa yang akan kamu dapatkan.” Dunia komputer tampak merupakan taman bermain yang liar dan indah, penuh dengan kemungkinan yang tak terbatas. Williams muda ketagihan.

“Saya sedang menulis program untuk diri saya sendiri, di atas kertas, untuk dijalankan di komputer di masa depan,” katanya. “Orang tua saya tidak benar -benar tahu harus berbuat apa dengan saya.”

Seiring bertambahnya usia, Williams maju dari komputer imajiner ke yang nyata. Selama dua tahun terakhir sekolah menengahnya, ia dipindahkan ke Sekolah Matematika dan Sains Alabama, sebuah sekolah asrama publik yang bergengsi, di mana ia pertama kali menemukan sisi teoretis ilmu komputer.

“Saya menyadari bahwa ada dunia yang lebih luas di luar sana, dan bahwa ada cara untuk berpikir secara matematis tentang komputer,” katanya. “Itulah yang ingin saya lakukan.”

Williams terutama tertarik pada cabang ilmu komputer teoritis yang disebut teori kompleksitas komputasi. Ini berkaitan dengan sumber daya (seperti ruang dan ruang) yang diperlukan untuk menyelesaikan masalah komputasi seperti menyortir daftar atau anjak nomor. Sebagian besar masalah dapat diselesaikan dengan banyak algoritma yang berbeda, masing -masing dengan tuntutan sendiri tepat waktu dan ruang. Para ahli teori kompleksitas mengurutkan masalah ke dalam kategori, yang disebut kelas kompleksitas, berdasarkan tuntutan sumber daya dari algoritma terbaik untuk menyelesaikannya – yaitu, algoritma yang berjalan tercepat atau menggunakan ruang paling sedikit.

Tetapi bagaimana Anda membuat studi tentang sumber daya komputasi secara matematis ketat? Anda tidak akan jauh jika Anda mencoba menganalisis waktu dan ruang dengan membandingkan menit dengan megabyte. Untuk membuat kemajuan, Anda harus mulai dengan definisi yang tepat.

Menjadi banyak akal

Definisi -definisi itu muncul dari karya Juris Hartmanis, seorang ilmuwan komputer perintis yang memiliki pengalaman melakukan dengan sumber daya yang terbatas. Ia dilahirkan pada tahun 1928 dari keluarga Latvia terkemuka, tetapi masa kecilnya terganggu oleh pecahnya Perang Dunia II. Menempati pasukan Soviet menangkap dan mengeksekusi ayahnya, dan setelah perang Hartmanis selesai sekolah menengah di sebuah kamp pengungsi. Dia pergi ke universitas, di mana dia unggul meskipun dia tidak mampu membeli buku teks.

“Saya mengkompensasi dengan membuat catatan yang sangat rinci dalam kuliah,” kenangnya di a Wawancara 2009. “Ada keuntungan tertentu [having] untuk mengimprovisasi dan mengatasi kesulitan. ” Hartmanis berimigrasi ke Amerika Serikat pada tahun 1949, dan mengerjakan serangkaian pekerjaan sambilan – membangun mesin pertanian, baja manufaktur dan bahkan melayani sebagai pelayan – sambil belajar matematika di Universitas Kansas City.

Pada tahun 1960, saat bekerja di General Electric Research Laboratory di Schenectady, New York, Hartmanis bertemu Richard Stearns, seorang mahasiswa pascasarjana yang melakukan magang musim panas. Dlm sepasang Breakbreaking dokumen Mereka menetapkan definisi matematika yang tepat untuk waktu dan ruang. Definisi -definisi ini memberi para peneliti bahasa yang mereka butuhkan untuk membandingkan kedua sumber daya dan mengurutkan masalah menjadi kelas kompleksitas.

Salah satu kelas terpenting berjalan dengan nama sederhana “P.” Secara kasar, itu mencakup semua masalah yang dapat diselesaikan dalam waktu yang wajar. Kelas kompleksitas analog untuk ruang dijuluki “pspace.”

Hubungan antara kedua kelas ini adalah salah satu pertanyaan sentral dari teori kompleksitas. Setiap masalah di P juga ada di PSPACE, karena algoritma cepat tidak punya cukup waktu untuk mengisi banyak ruang dalam memori komputer. Jika pernyataan sebaliknya juga benar, kedua kelas akan setara: ruang dan waktu akan memiliki kekuatan komputasi yang sebanding. Tetapi para ahli teori kompleksitas menduga bahwa PSPACE adalah kelas yang jauh lebih besar, yang mengandung banyak masalah yang tidak ada dalam P. Dengan kata lain, mereka percaya bahwa ruang adalah sumber komputasi yang jauh lebih kuat daripada waktu. Keyakinan ini berasal dari fakta bahwa algoritma dapat menggunakan potongan kecil yang sama berulang kali, sementara waktu tidak memaafkan – setelah itu berlalu, Anda tidak bisa mendapatkannya kembali.

“Intuisinya sangat sederhana,” kata Williams. “Kamu bisa menggunakan kembali ruang, tetapi kamu tidak bisa menggunakan kembali waktu.”

Tetapi intuisi tidak cukup baik untuk ahli teori kompleksitas: mereka menginginkan bukti yang ketat. Untuk membuktikan bahwa PSPACE lebih besar dari P, para peneliti harus menunjukkan bahwa untuk beberapa masalah di PSPACE, algoritma cepat secara kategoris tidak mungkin. Di mana mereka akan memulai?

Odyssey luar angkasa

Ketika itu terjadi, mereka mulai di Universitas Cornell, di mana Hartmanis pindah pada tahun 1965 untuk mengepalai departemen ilmu komputer yang baru didirikan. Di bawah kepemimpinannya dengan cepat menjadi pusat penelitian dalam teori kompleksitas, dan pada awal 1970 -an, sepasang peneliti di sana, John Hopcroft dan Wolfgang Paul, berangkat untuk membangun hubungan yang tepat antara waktu dan ruang.

Hopcroft dan Paul tahu bahwa untuk menyelesaikan masalah P versus PSPACE, mereka harus membuktikan bahwa Anda tidak dapat melakukan perhitungan tertentu dalam waktu yang terbatas. Tapi sulit untuk membuktikan negatif. Sebaliknya, mereka memutuskan untuk membalikkan masalah di kepalanya dan mengeksplorasi apa yang dapat Anda lakukan dengan ruang terbatas. Mereka berharap untuk membuktikan bahwa algoritma yang diberikan anggaran ruang tertentu dapat menyelesaikan semua masalah yang sama seperti algoritma dengan anggaran waktu yang sedikit lebih besar. Itu akan menunjukkan bahwa ruang setidaknya sedikit lebih kuat dari waktu – langkah kecil tapi perlu untuk menunjukkan bahwa pspace lebih besar dari P.

Dengan tujuan itu, mereka beralih ke metode yang oleh teori kompleksitas menyebut simulasi, yang melibatkan mengubah algoritma yang ada menjadi yang baru yang menyelesaikan masalah yang sama, tetapi dengan jumlah ruang dan waktu yang berbeda. Untuk memahami ide dasarnya, bayangkan Anda diberi algoritma yang cepat untuk abjad dari rak buku Anda, tetapi itu mengharuskan Anda untuk meletakkan buku -buku Anda dalam lusinan tumpukan kecil. Anda mungkin lebih suka pendekatan yang membutuhkan lebih sedikit ruang di apartemen Anda, bahkan jika itu membutuhkan waktu lebih lama. Simulasi adalah prosedur matematika yang bisa Anda gunakan untuk mendapatkan algoritma yang lebih cocok: beri makan aslinya, dan itu akan memberi Anda algoritma baru yang menghemat ruang dengan mengorbankan waktu.

Desainer algoritma telah lama mempelajari pertukaran ruang-waktu ini untuk tugas-tugas tertentu seperti menyortir. Tetapi untuk membangun hubungan umum antara waktu dan ruang, Hopcroft dan Paul membutuhkan sesuatu yang lebih komprehensif: prosedur simulasi hemat ruang yang berfungsi untuk setiap algoritma, tidak peduli masalah apa pun yang dipecahkannya. Mereka mengharapkan keumuman ini akan dikenakan biaya. Simulasi universal tidak dapat mengeksploitasi detail masalah spesifik apa pun, jadi mungkin tidak akan menghemat ruang sebanyak simulasi khusus. Tetapi ketika Hopcroft dan Paul memulai pekerjaan mereka, tidak ada metode universal yang diketahui untuk menghemat ruang sama sekali. Bahkan menghemat sejumlah kecil akan menjadi kemajuan.

Terobosan datang pada tahun 1975, setelah Hopcroft dan Paul bekerja sama dengan seorang peneliti muda bernama Leslie Valiant. Ketiganya dirancang a Prosedur Simulasi Universal Itu selalu menghemat sedikit ruang. Apa pun algoritma yang Anda berikan, Anda akan mendapatkan yang setara dengan anggaran ruangnya sedikit lebih kecil dari anggaran waktu algoritma asli.

“Apa pun yang dapat Anda lakukan dalam banyak waktu, Anda juga dapat melakukannya dalam ruang yang sedikit lebih sedikit,” kata Valiant. Itu adalah langkah besar pertama dalam pencarian untuk menghubungkan ruang dan waktu.

Tetapi kemudian kemajuan terhenti, dan para ahli teori kompleksitas mulai curiga bahwa mereka akan mencapai penghalang mendasar. Masalahnya justru karakter universal Hopcroft, Paul dan Valiant. Sementara banyak masalah dapat diselesaikan dengan ruang yang jauh lebih sedikit daripada waktu, beberapa secara intuitif tampak seperti mereka akan membutuhkan ruang sebanyak waktu. Jika demikian, lebih banyak simulasi universal yang efisien ruang tidak mungkin. Paul dan Dua peneliti lain segera membuktikan bahwa mereka memang tidak mungkinasalkan Anda membuat satu asumsi yang tampaknya jelas: potongan data yang berbeda tidak dapat menempati ruang yang sama dalam memori pada saat yang sama.

“Semua orang menerima begitu saja bahwa Anda tidak dapat melakukan yang lebih baik,” kata Wigderson.

Hasil Paul menyarankan agar menyelesaikan masalah P versus PSPACE akan membutuhkan simulasi yang sama sekali mendukung pendekatan yang berbeda, tetapi tidak ada yang punya ide bagus. Di situlah masalahnya bertahan selama 50 tahun – sampai Williams akhirnya memecahkan Logjam.

Pertama, dia harus lulus kuliah.

Kelas kompleksitas

Pada tahun 1996, saatnya tiba bagi Williams untuk mendaftar ke perguruan tinggi. Dia tahu bahwa mengejar teori kompleksitas akan membawanya jauh dari rumah, tetapi orang tuanya menjelaskan bahwa Pantai Barat dan Kanada keluar dari pertanyaan. Di antara pilihannya yang tersisa, Cornell menonjol kepadanya karena tempatnya yang menonjol dalam sejarah disiplin favoritnya.

“Orang ini Hartmanis mendefinisikan kelas waktu dan kompleksitas ruang,” kenangnya berpikir. “Itu penting bagi saya.”

Williams dirawat di Cornell dengan bantuan keuangan yang murah hati dan tiba pada musim gugur 1997, berencana untuk melakukan apa pun untuk menjadi ahli teori kompleksitas sendiri. Pikiran tunggal menonjol pada teman-temannya.

“Dia hanya super-duper dalam teori kompleksitas,” kata Scott Aaronsonseorang ilmuwan komputer di University of Texas, Austin, yang tumpang tindih dengan Williams di Cornell.

Tetapi pada tahun kedua, Williams berjuang untuk mengikuti kursus yang menekankan kekakuan matematika atas intuisi. Setelah dia mendapat nilai menengah di kelas tentang teori komputasi, guru menyarankan dia mempertimbangkan karier lain. Tapi Williams tidak akan melepaskan mimpinya. Dia menggandakan dan mendaftar dalam kursus teori pascasarjana, berharap bahwa nilai bintang di kelas yang lebih keras akan terlihat mengesankan pada aplikasi sekolah pascasarjana. Profesor yang mengajar bahwa kursus pascasarjana adalah Hartmanis, pada saat itu seorang negarawan yang lebih tua di lapangan.

Williams mulai menghadiri jam kantor Hartmanis setiap minggu, di mana ia hampir selalu menjadi satu -satunya siswa yang muncul. Kegigihannya terbayar: ia mendapatkan A dalam kursus, dan Hartmanis setuju untuk menasihatinya tentang proyek penelitian independen pada semester berikutnya. Pertemuan mingguan mereka berlanjut sepanjang waktu Williams di perguruan tinggi. Hartmanis mendorongnya untuk menumbuhkan pendekatan individu untuk penelitian kompleksitas dan dengan lembut menjauhkannya dari jalan buntu.

“Saya sangat dipengaruhi olehnya,” kata Williams. “Kurasa aku masih sekarang.”

Tetapi meskipun mendapatkan beasiswa penelitian lulusan yang didambakan dari National Science Foundation, Williams ditolak oleh setiap program doktoral yang ia lamar. Mendengar berita itu, Hartmanis menelepon seorang kolega, kemudian berbalik dan memberi selamat kepada Williams karena diterima dalam program master selama setahun di Cornell. Setahun kemudian Williams kembali mendaftar ke berbagai program doktoral, dan dengan pengalaman penelitian tambahan di bawah ikat pinggangnya, ia menemukan kesuksesan.

Williams terus bekerja dalam teori kompleksitas di sekolah pascasarjana dan tahun -tahun berikutnya. Pada 2010, empat tahun setelah menerima gelar doktor, ia membuktikan a Hasil tonggak sejarah—Sebuah langkah kecil, tetapi yang terbesar dalam beberapa dekade, menuju pemecahan pertanyaan paling terkenal dalam ilmu komputer teoretistentang sifat masalah keras. Hasil itu memperkuat reputasi Williams, dan ia kemudian menulis lusinan makalah lain tentang berbagai topik dalam teori kompleksitas.

P versus pspace bukan salah satunya. Williams telah terpesona oleh masalah ini sejak ia pertama kali bertemu di perguruan tinggi. Dia bahkan akan melengkapi kurikulum ilmu komputernya dengan kursus logika dan filosofi, mencari inspirasi dari perspektif lain tentang ruang dan waktu, tetapi tidak berhasil.

“Itu selalu ada di benak saya,” kata Williams. “Aku hanya tidak bisa memikirkan sesuatu yang cukup menarik untuk dikatakan tentang itu.”

Tahun lalu, dia akhirnya menemukan kesempatan yang dia tunggu -tunggu.

Kerikil licin

Kisah hasil baru Williams dimulai dengan kemajuan pada pertanyaan yang berbeda tentang memori dalam perhitungan: masalah apa yang dapat diselesaikan dengan ruang yang sangat terbatas? Pada 2010, ahli teori kompleksitas perintis Stephen Cook dan kolaboratornya menemukan tugas, yang disebut Masalah evaluasi pohonbahwa mereka terbukti tidak mungkin untuk algoritma apa pun dengan anggaran ruang di bawah ambang batas tertentu. Tapi ada celah. Buktinya mengandalkan asumsi akal sehat yang sama bahwa Paul dan rekan -rekannya telah membuat beberapa dekade sebelumnya: algoritma tidak dapat menyimpan data baru di ruang yang sudah penuh.

Selama lebih dari satu dekade, para ahli teori kompleksitas mencoba untuk menutup celah itu. Kemudian, pada tahun 2023, Putra Cook James dan seorang peneliti bernama Ian Mertz meniupnya terbuka lebar, merancang algoritma yang memecahkan masalah evaluasi pohon menggunakan jauh lebih sedikit ruang dari yang dipikirkan siapa pun. Bukti cook penatua telah mengasumsikan bahwa bit data seperti kerikil yang harus menempati tempat terpisah dalam memori algoritma. Tapi ternyata itu bukan satu -satunya cara untuk menyimpan data. “Kita benar -benar dapat berpikir tentang kerikil ini sebagai hal -hal yang bisa kita sukai sedikit di atas satu sama lain,” kata Beame.

Algoritma Cook dan Mertz membangkitkan rasa ingin tahu banyak peneliti, tetapi tidak jelas bahwa ia memiliki aplikasi di luar masalah evaluasi pohon. “Tidak ada yang melihat betapa sentralnya waktu versus ruang itu sendiri,” kata Wigderson.

Ryan Williams adalah pengecualian. Pada musim semi 2024, sekelompok siswa memberikan presentasi tentang kertas Cook dan Mertz sebagai proyek akhir mereka di kelas yang ia ajarkan. Antusiasme mereka menginspirasi dia untuk melihat lebih dekat. Begitu dia melakukannya, sebuah ide melompat padanya. Metode Cook dan Mertz, ia sadari, benar-benar alat tujuan umum untuk mengurangi penggunaan ruang. Mengapa tidak menggunakannya untuk memberi kekuatan simulasi universal baru yang menghubungkan waktu dan ruang – seperti yang dirancang oleh Hopcroft, Paul dan Valiant, tetapi lebih baik?

Hasil klasik itu adalah cara untuk mengubah algoritma apa pun dengan anggaran waktu tertentu menjadi algoritma baru dengan anggaran ruang yang sedikit lebih kecil. Williams melihat bahwa simulasi berdasarkan kerikil licin akan membuat penggunaan ruang algoritma baru jauh lebih kecil – hampir sama dengan akar kuadrat dari anggaran waktu algoritma asli. Algoritma hemat ruang baru itu juga akan jauh lebih lambat, sehingga simulasi tidak mungkin memiliki aplikasi praktis. Tetapi dari sudut pandang teoretis, itu bukan revolusioner.

Selama 50 tahun, para peneliti menganggap tidak mungkin untuk meningkatkan simulasi universal Hopcroft, Paul dan Valiant. Ide Williams – jika berhasil – tidak hanya akan mengalahkan catatan mereka – itu akan menghancurkannya.

“Saya memikirkannya, dan saya seperti, ‘Yah, itu tidak bisa benar,’” kata Williams. Dia mengesampingkannya dan tidak kembali ke sana sampai hari yang menentukan pada bulan Juli, ketika dia mencoba menemukan cacat dalam argumen dan gagal. Setelah dia menyadari bahwa tidak ada cacat, dia menghabiskan waktu berbulan -bulan menulis dan menulis ulang bukti untuk membuatnya sejelas mungkin.

Pada akhir Februari, akhirnya Williams Letakkan kertas yang sudah jadi secara online. Masak dan Mertz sama terkejutnya dengan orang lain. “Aku harus pergi berjalan -jalan sebelum melakukan hal lain,” kata Mertz.

Valiant mendapat pratinjau diam-diam tentang peningkatan Williams pada hasilnya yang sudah lama berpuluh-puluh tahun selama perjalanan pagi hari. Selama bertahun -tahun, dia diajarkan di Universitas Harvard, di ujung jalan dari kantor Williams di MIT. Mereka telah bertemu sebelumnya, tetapi mereka tidak tahu mereka tinggal di lingkungan yang sama sampai mereka bertemu satu sama lain di bus pada hari Februari yang bersalju, beberapa minggu sebelum hasilnya adalah publik. Williams menggambarkan buktinya kepada Valiant yang kaget dan berjanji untuk mengirim kertasnya.

“Saya sangat, sangat terkesan,” kata Valiant. “Jika Anda mendapatkan hasil matematika apa pun yang merupakan hal terbaik dalam 50 tahun, Anda harus melakukan sesuatu dengan benar.”

Pspace: perbatasan terakhir

Dengan simulasi barunya, Williams telah membuktikan hasil positif tentang kekuatan komputasi ruang: algoritma yang menggunakan ruang yang relatif sedikit dapat menyelesaikan semua masalah yang membutuhkan waktu yang agak lebih besar. Kemudian, menggunakan hanya beberapa baris matematika, ia membalikkannya dan membuktikan hasil negatif tentang kekuatan komputasi waktu: setidaknya beberapa masalah tidak dapat diselesaikan kecuali Anda menggunakan lebih banyak waktu daripada ruang. Hasil kedua dan lebih sempit itu sejalan dengan apa yang diharapkan para peneliti. Bagian yang aneh adalah bagaimana Williams sampai di sana, dengan terlebih dahulu membuktikan hasil yang berlaku untuk semua algoritma, tidak peduli masalah apa pun yang mereka selesaikan.

“Saya masih kesulitan mempercayainya,” kata Williams. “Sepertinya terlalu bagus untuk menjadi kenyataan.”

Disebarkan dalam istilah kualitatif, hasil kedua Williams mungkin terdengar seperti solusi yang telah lama dicari untuk masalah P versus PSPACE. Perbedaannya adalah masalah skala. P dan PSPACE adalah kelas kompleksitas yang sangat luas, sementara hasil Williams bekerja pada tingkat yang lebih baik. Dia membangun kesenjangan kuantitatif antara kekuatan ruang dan kekuatan waktu, dan untuk membuktikan bahwa pspace lebih besar dari P, para peneliti harus membuat celah itu jauh, jauh lebih lebar.

Itu tantangan yang menakutkan, mirip dengan mencabut celah trotoar dengan linggis sampai selebar Grand Canyon. Tetapi mungkin untuk sampai ke sana dengan menggunakan versi yang dimodifikasi dari prosedur simulasi Williams yang mengulangi langkah kunci berkali -kali, menghemat sedikit ruang setiap kali. Ini seperti cara untuk berulang kali meningkatkan panjang linggis Anda – membuatnya cukup besar, dan Anda dapat membuka apa pun. Peningkatan berulang itu tidak berfungsi dengan versi algoritma saat ini, tetapi para peneliti tidak tahu apakah itu batasan mendasar.

“Ini bisa menjadi hambatan utama, atau bisa menjadi hambatan 50 tahun,” kata Valiant. “Atau bisa jadi sesuatu yang mungkin bisa diselesaikan seseorang minggu depan.”

Jika masalah diselesaikan minggu depan, Williams akan menendang dirinya sendiri. Sebelum dia menulis surat kabar itu, dia menghabiskan waktu berbulan -bulan mencoba dan gagal memperpanjang hasilnya. Tetapi bahkan jika ekstensi seperti itu tidak mungkin, Williams yakin bahwa lebih banyak eksplorasi ruang angkasa pasti akan memimpin di suatu tempat yang menarik – mungkin kemajuan pada masalah yang sama sekali berbeda.

“Saya tidak pernah bisa membuktikan dengan tepat hal -hal yang ingin saya buktikan,” katanya. “Tetapi sering kali, hal yang saya buktikan jauh lebih baik dari apa yang saya inginkan.”

Catatan Editor: Scott Aaronson adalah anggota majalah Quanta’s Dewan Penasehat.

Cerita asli dicetak ulang dengan izin dari Berapa banyak majalahpublikasi editorial independen dari Yayasan Simons yang misinya adalah untuk meningkatkan pemahaman publik tentang sains dengan meliput perkembangan penelitian dan tren matematika dan ilmu fisik dan kehidupan.