Avi Wigderson 40 yılı aşkın süredir problemler üzerinde çalışıyor. Ancak bir hesaplamalı karmaşıklık teorisyeni olarak, bu sorunların yanıtlarını pek de önemsemiyor. Çoğu zaman bunların çözülebilir olup olmadığını ve bunu nasıl anlayacağını bilmek istiyor. "Durum çok komik" dedi WigdersonPrinceton, New Jersey'deki İleri Araştırma Enstitüsü'nde bilgisayar bilimcisi. Bir soru ne kadar zor görünürse görünsün, onu yanıtlamanın etkili bir yolu ulaşılamayacak bir yerde saklanıyor olabilir. “Bildiğimiz kadarıyla karşılaştığımız ve çözmeye çalıştığımız her problemin, onu çözebilecek bir algoritması olduğu ihtimalini göz ardı edemeyiz. Benim için en ilginç sorun bu.”

Bugün Wigderson yarışmanın galibi seçildi. AM Turing Ödülühesaplama teorisine yaptığı temel katkılardan dolayı bilgisayar bilimlerinde en büyük ödüllerden biri olarak kabul edilmektedir. Wigderson'un çalışmaları alanın neredeyse her alanına dokundu. Meslektaşları, işbirlikçileri ve mentileri, farklı alanlar arasında sürekli olarak beklenmedik köprüler bulduğunu söylüyor. Rastgelelik ve hesaplama üzerine 1990'larda başlayan çalışması, matematik ile bilgisayar bilimi arasındaki günümüz araştırmalarının temelini oluşturan derin bağlantıları ortaya çıkardı.

Madhu SudanHarvard Üniversitesi'nden 2002 Rolf Nevanlinna Ödülü'nü (şimdi Abacus Ödülü olarak anılıyor) kazanan bilgisayar bilimcisi Wigderson'ın bu alandaki etkisinin gözden kaçırılmaması gerektiğini söyledi. Sudan, "Bilgisayar biliminin herhangi bir alanında Avi'nin çalışmalarıyla kesişmeden çalışmak çok zor" dedi. “Ve her yerde çok derin içgörüler buluyorsunuz.” Örneğin 1980'lerin sonlarında Sudan, belirli matematiksel fonksiyonlar ve polinomlar arasındaki bağlantıları araştıran bir makale üzerinde Wigderson'la birlikte çalıştı. Bu çalışma Sudan'ın tüm kariyerini başlattı. Sudan, "Bu Avi için tipik bir durum" dedi. "Biraz boşluğa giriyor, doğru soruları soruyor ve sonra yoluna devam ediyor."

Wigderson, İsrail'in Hayfa kentinde, Holokost'tan sağ kurtulan bir hemşire ve bir elektrik mühendisinin üç oğlundan biri olarak büyüdü. Babası bulmacaları seviyordu ve çocuklarıyla paylaştığı matematiğin temel fikirleriyle yoğun bir şekilde ilgileniyordu. Wigderson, "Bu virüsün bana bulaştığı adam o" dedi. 1970'lerde Hayfa'daki Technion'da üniversiteye başladığında matematik alanında uzmanlaşmak istedi ancak ailesi onu bunun yerine bilgisayar bilimine yönlendirdi. "İşim bittiğinde bir işim olmasının iyi bir fikir olabileceğini düşündüler" dedi.

Derin, cevaplanmamış, özünde matematik olan sorularla dolu bir alan buldu. İlk çığır açıcı çabalarından biri görünüşteki bir çelişkiye odaklanıyordu: Bir başkasını, nasıl olduğunu göstermeden matematiksel bir ifadenin kanıtlandığına ikna etmenin mümkün olup olmadığı.

"Kanıtı gören kişi kanıtın kendisi hakkında hiçbir şey öğrenmez" dedi Raz koştuPrinceton Üniversitesi'nde bilgisayar bilimcisi. 1985 yılında Shafi Goldwasser, Silvio Micali ve Charles Rackoff bu kavramı ortaya attılar. sıfır bilgi etkileşimli kanıtları, birkaç ifade için kullanımını gösteriyor. Wigderson, Micali ve Oded Goldreich ile birlikte daha sonra bu fikri açıkladılar ve eğer bir ifade kanıtlanabiliyorsa, bunun mümkün olduğunu gösteren koşulları ortaya koydular. ayrıca sıfır bilgi kanıtı da var.

“Bu, kriptografide önemli bir sonuçtur; son derece merkezi," dedi Raz. Sıfır bilgi kanıtını kullanarak, birisi gizli anahtarını kullanarak bir mesajı doğru şekilde şifrelediğini veya imzaladığını, bununla ilgili herhangi bir bilgi vermeden kanıtlayabilir. "Avi'nin kriptografide bazı son derece önemli sonuçları var ve bu belki de onlardan en önemlisi."

Ancak Wigderson'un belki de en temel sonucu başka bir alanda yatmaktadır: hesaplama sertliğini rasgelelik. 1970'lerin sonlarına gelindiğinde bilgisayar bilimcileri, birçok zor problem için, olasılıksal algoritmalar olarak da adlandırılan rastgelelik kullanan algoritmaların, deterministik alternatiflerini büyük ölçüde geride bırakabileceğini fark ettiler. İçinde 1977 kanıtıÖrneğin Robert Solovay ve Volker Strassen, bir sayının o zamanın en iyi deterministik algoritmalarından daha hızlı asal olup olmadığını belirleyebilecek rastgele bir algoritma geliştirdiler.

Bazı problemler için olasılıksal algoritmalar deterministik algoritmalara işaret edebilir. 1980'lerin başında Wigderson, Berkeley'deki Kaliforniya Üniversitesi'nden Richard Karp ile birlikte çalışarak rastgelelik fikrini hesaplama açısından zor kabul edilen problemlerle ilişkilendirdi; bu, bilinen hiçbir deterministik algoritmanın bunları makul bir sürede çözemeyeceği anlamına geliyor. Wigderson, "Zor olduklarını nasıl kanıtlayacağımızı bilmiyoruz" dedi. Ancak o ve Karp, belirli bir zor problem için rastgeleleştirilmiş bir algoritma buldular ve bunu daha sonra rastgelelikten arındırarak bunun için etkili bir deterministik algoritmayı ortaya çıkardılar. Aynı sıralarda diğer araştırmacılar, kriptografi problemlerindeki hesaplama sertliği varsayımlarının genel olarak rastgelelikten arındırmayı nasıl mümkün kılabileceğini gösterdi.

Rastgeleliğin mantıksız etkinliği, onu rastgeleliğin doğası hakkında düşünmeye yöneltti. O da o dönemdeki diğer araştırmacılar gibi etkili problem çözümü için bunun ne kadar gerekli olduğunu ve hangi koşullar altında tamamen ortadan kaldırılabileceğini sorguladı. "Başlangıçta bunun yalnızca bizim aptallığımız olup olmadığı, rastgeleliği ortadan kaldıramayacağımız açık değildi" dedi. “Fakat asıl soru, rastgeleliğin her zaman verimli bir şekilde ortadan kaldırılıp kaldırılamayacağıydı.” Rastgelelik ihtiyacının problemin hesaplama zorluğuyla yakından bağlantılı olduğunu fark etti.

bir için 1994 kağıto ve bilgisayar bilimcisi Noam Nisan bu bağlantıyı aydınlattı. Çoğu bilgisayar bilimcinin şüphelendiği gibi herhangi bir doğal zor problem varsa, her verimli rastgele algoritmanın verimli bir deterministik algoritmayla değiştirilebileceğini kanıtladılar. Wigderson, "Rastgeleliği her zaman ortadan kaldırabilirsiniz" dedi.

Daha da önemlisi, deterministik algoritmaların "sözde rastgele" dizileri (rastgele görünen ancak öyle olmayan veri dizileri) kullanabileceğini buldular. Ayrıca herhangi bir zor problemin sahte rastgele oluşturucu oluşturmak için nasıl kullanılabileceğini de gösterdiler. Olasılıksal bir algoritmaya sözde rastgele bitlerin (rastgele olanlar yerine) beslenmesi, aynı problem için etkili bir deterministik bit ile sonuçlanacaktır.

Sudan, makalenin bilgisayar bilimcilerinin zor problemlerin inceliklerini ve bunların nasıl çözüleceğini ortaya çıkarmaya yardımcı olabilecek rastgelelik derecelerini tanımalarına yardımcı olduğunu söyledi. "Bu sadece rastlantısallık değil, aynı zamanda rastlantısallığın algılanmasıdır" dedi. "Anahtar bu."

Sudan, rastlantısallığın her yerde ortaya çıktığını ancak aslında bulmanın son derece zor olduğunu belirtiyor. "İnsanlar size pi'nin rakamlarının rastgele göründüğünü veya asal sayılar dizisinin rastgele göründüğünü söylüyor" dedi. “Tamamen kararlılar ama bize rastgele görünüyorlar.” Rastgelelik algısının günümüz bilgisayar biliminin kalbinde yer aldığını söyledi. "Ve bu Avi'nin büyük ölçüde teşvik ettiği bir şey."

Rastgelelik, karmaşıklık teorisinde güçlü bir kaynak haline geldi, ancak bulunması zor. Wigderson, yazı tura atmaların ve zar atmaların gerçekten rastgele olmadığına dikkat çekiyor: Fiziksel sistem hakkında yeterli bilgiye sahipseniz, sonuç tamamen tahmin edilebilir. Mükemmel rastgeleliğin anlaşılması zor ve doğrulanması zor olduğunu söyledi.

Ancak Wigerson'a göre bilgi işlem örnekleri her yerde; yalnızca akıllı telefonlarda, dizüstü bilgisayarlarda ve şifreleme algoritmalarında değil, aynı zamanda biyolojik ve fiziksel sistemlerde de. Son yıllarda, hesaplama teorisinden elde edilen bulgular, kuş sürüsü ve seçim sonuçlarından vücuttaki biyokimyasal reaksiyonlara kadar bir dizi beklenmedik soruna dair içgörüler sağladı. "Temel olarak herhangi bir doğal süreç, hesaplama olarak görebileceğiniz bir evrimdir, dolayısıyla onu bu şekilde inceleyebilirsiniz. Neredeyse her şey hesaplanıyor.”