Selama lebih dari 40 tahun, Avi Wigderson telah mempelajari permasalahan. Namun sebagai ahli teori kompleksitas komputasi, dia tidak serta merta peduli dengan jawaban atas permasalahan tersebut. Dia sering kali hanya ingin tahu apakah masalah tersebut dapat dipecahkan atau tidak, dan bagaimana cara mengetahuinya. “Situasinya konyol,” kata Wigderson, seorang ilmuwan komputer di Institute for Advanced Study di Princeton, New Jersey. Tidak peduli betapa sulitnya sebuah pertanyaan, cara efisien untuk menjawabnya mungkin adalah dengan bersembunyi di luar jangkauan. “Sejauh yang kami tahu, untuk setiap masalah yang kami hadapi dan coba selesaikan, tidak menutup kemungkinan ada algoritma yang bisa menyelesaikannya. Ini adalah satu-satunya masalah yang paling menarik bagi saya.”

Hari ini Wigderson dinobatkan sebagai pemenang Penghargaan AM Turing, yang secara luas dianggap sebagai salah satu penghargaan tertinggi dalam ilmu komputer, atas kontribusi mendasarnya pada teori komputasi. Karya Wigderson telah menyentuh hampir setiap bidang bidang. Rekan-rekan, kolaborator, dan peserta didiknya mengatakan bahwa dia secara konsisten menemukan jembatan tak terduga antara bidang-bidang yang berbeda. Dan karyanya mengenai keacakan dan komputasi, yang dimulai pada tahun 1990an, mengungkap hubungan mendalam antara matematika dan ilmu komputer yang mendasari penyelidikan saat ini.

Madhu Sudan, seorang ilmuwan komputer di Universitas Harvard yang memenangkan Hadiah Rolf Nevanlinna tahun 2002 (sekarang disebut Hadiah Abacus), mengatakan pengaruh Wigderson di bidang ini tidak mungkin diabaikan. “Sangat sulit untuk bekerja di bidang ilmu komputer apa pun tanpa benar-benar bersinggungan dengan pekerjaan Avi,” kata Sudan. “Dan di mana pun, Anda menemukan wawasan yang sangat mendalam.” Pada akhir tahun 1980-an, misalnya, Sudan bekerja sama dengan Wigderson dalam sebuah makalah yang menyelidiki hubungan antara fungsi matematika tertentu dan polinomial. Pekerjaan itu meluncurkan seluruh karier Sudan. “Ini tipikal Avi,” kata Sudan. “Dia mendapat ruang, dia menanyakan pertanyaan yang tepat, dan kemudian melanjutkan.”

Wigderson dibesarkan di Haifa, Israel, sebagai salah satu dari tiga putra seorang perawat dan insinyur listrik, keduanya selamat dari Holocaust. Ayahnya menyukai teka-teki dan sangat tertarik pada ide-ide dasar matematika, yang ia bagikan kepada anak-anaknya. “Dialah orang yang membuat saya tertular virus ini,” kata Wigderson. Ketika ia mulai kuliah pada tahun 1970-an, di Technion di Haifa, ia ingin mengambil jurusan matematika, namun orang tuanya malah mengarahkannya ke ilmu komputer. “Mereka mengira mungkin merupakan ide bagus jika saya mempunyai pekerjaan setelah saya selesai,” katanya.

Dia menemukan bidang yang kaya dengan pertanyaan-pertanyaan mendalam dan belum terjawab yang bersifat matematis. Salah satu upaya terobosannya yang paling awal berfokus pada kontradiksi yang tampak: apakah mungkin meyakinkan orang lain bahwa pernyataan matematis telah dibuktikan tanpa menunjukkan caranya.

“Orang yang melihat buktinya tidak mengetahui apa pun tentang bukti itu sendiri,” kata Ran Raz, seorang ilmuwan komputer di Universitas Princeton. Pada tahun 1985, Shafi Goldwasser, Silvio Micali, dan Charles Rackoff memperkenalkan konsep ini bukti interaktif tanpa pengetahuan, menunjukkan penggunaannya untuk beberapa pernyataan. Wigderson, bersama Micali dan Oded Goldreich, kemudian menguraikan gagasan tersebut, dengan memberikan syarat-syarat yang menunjukkan bahwa jika suatu pernyataan dapat dibuktikan, maka pernyataan itu dapat dibuktikan. juga memiliki bukti tanpa pengetahuan.

“Ini adalah hasil utama dalam kriptografi; ini sangat sentral,” kata Raz. Dengan menggunakan bukti tanpa pengetahuan, seseorang dapat membuktikan bahwa mereka mengenkripsi atau menandatangani pesan dengan benar menggunakan kunci rahasianya, tanpa mengungkapkan informasi apa pun tentangnya. “Avi memiliki beberapa hasil yang sangat penting dalam kriptografi, dan ini mungkin yang paling penting.”

Namun mungkin hasil paling mendasar dari Wigderson terletak pada bidang lain: menghubungkan kekerasan komputasi dengan keserampangan. Pada akhir tahun 1970-an, para ilmuwan komputer telah menyadari bahwa untuk banyak permasalahan sulit, algoritme yang menggunakan keacakan, yang juga disebut algoritme probabilistik, dapat jauh mengungguli alternatif deterministiknya. Di sebuah Bukti 1977, misalnya, Robert Solovay dan Volker Strassen memperkenalkan algoritme acak yang dapat menentukan apakah suatu bilangan prima lebih cepat daripada algoritme deterministik terbaik saat itu.

Untuk beberapa masalah, algoritma probabilistik dapat menunjuk pada algoritma deterministik. Pada awal tahun 1980-an, Wigderson bekerja sama dengan Richard Karp dari University of California, Berkeley, untuk menghubungkan gagasan keacakan dengan permasalahan yang dianggap sulit secara komputasi, yang berarti tidak ada algoritme deterministik yang diketahui dapat menyelesaikannya dalam jangka waktu yang wajar. “Kami tidak tahu bagaimana membuktikannya sulit,” kata Wigderson. Namun, dia dan Karp menemukan algoritme acak untuk permasalahan sulit tertentu yang kemudian dapat mereka derandomisasi, yang secara efektif mengungkap algoritme deterministik untuk permasalahan tersebut. Sekitar waktu yang sama, peneliti lain menunjukkan bagaimana asumsi kekerasan komputasi dalam masalah kriptografi dapat memungkinkan derandomisasi secara umum.

Efektivitas keacakan yang tidak masuk akal membuatnya berpikir tentang sifat keacakan itu sendiri. Dia, seperti peneliti lain pada saat itu, mempertanyakan seberapa penting hal tersebut untuk pemecahan masalah yang efisien dan dalam kondisi apa hal tersebut dapat dihilangkan sama sekali. “Awalnya tidak jelas apakah ini hanya kebodohan kita sendiri, keacakan tidak bisa kita hilangkan,” ujarnya. “Tetapi pertanyaan yang lebih besar adalah apakah keacakan selalu dapat dihilangkan secara efisien atau tidak.” Dia menyadari bahwa kebutuhan akan keacakan terkait erat dengan kesulitan komputasi dari soal tersebut.

Untuk kertas 1994, dia dan ilmuwan komputer Noam Nisan menjelaskan hubungan itu. Mereka membuktikan bahwa jika ada masalah alami yang sulit, seperti dugaan sebagian besar ilmuwan komputer, maka setiap algoritma acak yang efisien dapat digantikan oleh algoritma deterministik yang efisien. “Anda selalu bisa menghilangkan keacakan,” kata Wigderson.

Yang penting, mereka menemukan bahwa algoritme deterministik mungkin menggunakan urutan “acak semu” — rangkaian data yang tampak acak padahal sebenarnya tidak. Mereka juga menunjukkan bagaimana permasalahan sulit apa pun dapat digunakan untuk membangun generator pseudorandom. Memasukkan bit pseudorandom (bukan bit acak) ke dalam algoritma probabilistik akan menghasilkan algoritma deterministik yang efisien untuk masalah yang sama.

Sudan mengatakan bahwa kertas membantu ilmuwan komputer mengenali tingkat keacakan yang dapat membantu mengungkap seluk-beluk permasalahan sulit dan cara menyelesaikannya. “Ini bukan hanya keacakan tapi persepsi keacakan,” katanya. “Itulah kuncinya.”

Sudan menyatakan bahwa keacakan nampaknya muncul di mana-mana namun, kenyataannya, sangat sulit ditemukan. “Orang bilang angka pi terlihat acak, atau barisan bilangan prima terlihat acak,” ujarnya. “Mereka sepenuhnya ditentukan, tetapi bagi kami mereka tampak acak.” Persepsi tentang keacakan, katanya, merupakan inti ilmu komputer saat ini. “Dan itu adalah sesuatu yang Avi promosikan secara luas.”

Keacakan telah menjadi sumber daya yang kuat dalam teori kompleksitas, namun sulit dipahami. Pelemparan koin dan pelemparan dadu, kata Wigderson, tidak sepenuhnya acak: Jika Anda memiliki cukup informasi tentang sistem fisik, maka hasilnya sepenuhnya dapat diprediksi. Keacakan yang sempurna, katanya, sulit dipahami dan sulit diverifikasi.

Namun bagi Wigerson, contoh komputasi ada di mana-mana – tidak hanya di ponsel pintar dan laptop serta algoritma enkripsi, namun juga di sistem biologis dan fisik. Dalam beberapa dekade terakhir, temuan dari teori komputasi telah menghasilkan wawasan mengenai berbagai masalah yang tidak terduga, mulai dari kawanan burung dan hasil pemilu hingga reaksi biokimia dalam tubuh. “Pada dasarnya, setiap proses alam adalah sebuah evolusi yang dapat Anda lihat sebagai komputasi, sehingga Anda dapat mempelajarinya seperti itu. Hampir semuanya dihitung.”