Turing Ödülü sahibi için her şey hesaplamadan ibaret ve bazı sorunlar çözülemez

Avi Wigderson'un rastgelelik üzerine öncü çalışması, bazı sorunların en güçlü bilgisayarların bile ötesinde olabileceği fikrini ileri sürdü.

2024 ACM Turing Ödülü sahibi Avi Wigderson, P=NP sorusuyla ilgili olarak "Bu şimdiye kadar sorulan en temel entelektüel sorulardan biri" diyor. "Eğer herkes yanılıyorsa ve P, NP'ye eşitse, bunun şaşırtıcı sonuçları olur."

Bilgisayar Makineleri Birliği (ACM) Çarşamba günü bu yılki A.M. ödülünü verdiğini duyurdu. Genellikle Nobel Bilgisayar Ödülü olarak anılan Turing ödülü, Princeton, New Jersey'deki İleri Araştırmalar Enstitüsü'nden bilgisayar bilimcisi ve matematikçi Avi Wigderson'a verilmiştir.

ACM'ye göre Wigderson, "hesaplamada rastgeleliğin rolüne ilişkin anlayışımızı yeniden şekillendirme" ve "teorik bilgisayar biliminde onlarca yıllık entelektüel liderlik" konusunda özel bir ayrıcalıkla, Hesaplama Teorisi olarak bilinen şeyi geliştiren temel katkılardan dolayı tanındı.

Adını İngiliz matematikçi ve bilgisayar bilimcisi Alan M. Turing'den alan ödül, Google'ın sağladığı mali destekle birlikte 1 milyon dolarlık bir ödülle birlikte geliyor.

Enstitüdeki Herbert H. Maass Profesörü Wigderson, onlarca yıldır hesaplamanın makinelerden daha fazlası olduğu konusunda derin bir anlayış sergiledi. Hesaplama evrenin her yerinde bulunan bir olgudur.

Wigderson, ZDNET ile yaptığı röportajda "Hesaplama gerçekten temel bir kavramdır" dedi. "Bilgisayarlardaki yalnızca algoritmalar değil: her şey hesaplanıyor."

"Kumsalda dikkat çekici bir desene sahip bir deniz kabuğu gördüğünüzde, bu son derece basit adımlarla hesaplanmıştır: Tek bir taneden büyümüştür ve yerel olarak bu taneler komşu taneleri hesaplamış ve birbirine bağlanmıştır; bu gerçekten basit süreç, onu geliştirdiğinizde harika desenler elde edersiniz."

Wigderson, "çok iyi bildiğimiz" yerel, artımlı değişimin bu basit kurallarının "çok karmaşık fenomenler yaratabileceğini" söyledi. Hesaplamalı örnekler çoktur. Hesaplama, döllenmiş yumurtanın nasıl insana dönüştüğü veya insan hücrelerinin kişinin yaşamı boyunca nasıl bölündüğüdür. Wigderson, "Ayrıca dedikodu" diye ekledi. "Size veya Facebook'ta söylenen bir şeyi, bilginin nasıl geliştiğini anlattığınızda, bunlar tam hesaplamalı modellerle çerçevelenebilecek hesaplamalı sorulardır."

Turing ödülünü Wigderson'a vermek özellikle uygundur çünkü onun alanı olan Hesaplama Teorisi, Turing tarafından 1936'da Turing'in çığır açan makalesi "Hesaplanabilir Sayılar Üzerine, Entscheidungsproblem'e Bir Uygulamayla" başlatılmıştır.

Turing, hesaplamanın, "çevre"nin insanlar, galaksiler, kumsaldaki deniz kabukları, bilgi veya herhangi bir sayıda olgu olabileceği, yerel, artımlı değişiklikler yoluyla bir ortamın evrimi olarak son derece geniş tanımının temelini attı.

Wigderson ve meslektaşları tarafından onlarca yıldır geliştirilen Turing'in merceğinden bakıldığında, her doğal olay hesaplamadır. Wigderson, "Termitler bu kaleleri nasıl inşa ediyor ya da bir şekilde nereye gidip bal arayacaklarını bilen arılar, aslında çok küçük beyin hücrelerine sahip olmalarına rağmen yaratmak üzere evrimleşiyorlar" diye açıkladı.

Ödül, Wigderson'a özellikle hesaplamada rastgeleliğin oynadığı rolün anlaşılmasına yaptığı katkı nedeniyle veriliyor. Ana bilgisayarlardan iPhone'lara kadar geleneksel bilgisayarlar "deterministiktir"; yani öngörülebilir bir adım dizisini takip ediyorlar. Ancak doğadaki en ilgi çekici hesaplama örneklerinin çoğu, deniz kabuğundan mırıltı olarak bilinen sığırcık sürülerine kadar rastlantısallık unsurlarını içerir.

Wigderson ve işbirlikçileri, hangi problemlerin "verimli bir şekilde" hesaplanıp hesaplanamayacağına dair anlayışı ilerletmek için rastgeleliğin araştırılmasını kullandılar. Dünyada bilimde, matematikte ve mühendislikte bilinen etkili algoritmaların bulunmadığı çok sayıda problem var; bu, üstel zaman yerine "polinom zamanda" çalışabilen bir algoritma anlamına geliyor.

Örneğin, büyük tam sayıların asal çarpanlarına ayrılmasının üstel süreden daha kısa sürede çalışabilen bilinen bir algoritması yoktur. Ancak böyle bir algoritmayı bulmak yeterli değil; Bilgisayar bilimcileri ve matematikçiler, bu tür "zor" problemler için bir çözümün var olup olamayacağını kanıtlamak, öyle ya da böyle kesin olarak bilmek istiyorlar.

Wigderson, ZDNET'e ACM tarafından alıntı yapılan üç ana makalenin bir dizi, bir ilerleme oluşturduğunu söyledi.

Wigderson, "Soru, algoritmalarda rastgeleliğin ne kadar güçlü olduğuydu" dedi. Seksenli yıllardan başlayarak bilgisayar bilimcileri, verimli algoritmalara giden bir rota olarak rastgeleliği kullanmanın birçok yolunu bulmuşlardı, "Ve böylece rastgelelik çok güçlü gibi görünüyordu."

"Bu çalışmalar rastgeleliğin o kadar da güçlü olmadığını göstermeyi amaçlıyordu" dedi. Bunun yerine Wigderson ve meslektaşları, bazı zor problemleri etkili ve deterministik bir şekilde çözebilecek sözde rasgele sayı üreteçleri geliştirdiler.

"Tüm bu makalelerde, zor bir problemi ele alıyorsunuz ve rastgele görünen bitleri deterministik olarak üretebilen bir sözde rastgele oluşturucu yaratıyorsunuz ve olasılıksal bir algoritmadaki rastgele girdileri deterministik bir algoritmayla değiştirebiliyorsunuz."

Rastgeleliğin ayıklanıp yerine deterministik bir yaklaşım getirilmesi, en karmaşık sözde rastgele oluşturucunun ortaya çıktığı son makaleyle sonuçlandı. Wigderson derste şunları kaydetti: "Herhangi bir polinom zamanlı olasılıksal algoritmanın, polinom zamanlı deterministik bir algoritmaya dönüştürülebileceği sonucuna varabiliriz."

Bu keşiflerin şaşırtıcı bir yan etkisi, eğer bir algoritmadan rastgeleliği kaldırabilirseniz, problemin zorluğunu kanıtlayabilirsiniz; bir problemin zor olup olmadığı sorusunu çözmenin çarpıcı bir arka kapı yolu. .

Wigderson, "Bir şekilde çok farklı olan bu iki kavram (rastgelelik ve sertlik) birbiriyle yakından bağlantılı" dedi. "Neredeyse aynı şeyler. Olasılıksal algoritmalardan rastgeleliği çıkarmak ve hesaplama problemlerinin sertliğini kanıtlamak bir nevi ikili problemlerdir."

Rastgelelik üzerine çalışmayı daha derinlemesine incelemek isteyenler için makaleler aşağıda listelenmiştir. Bununla birlikte, Wigderson'un ücretsiz olarak indirilebilen geniş cildi "Matematik ve Hesaplama"da rastgelelik hakkındaki bölümü okuyabilirsiniz. Eğer bu kitaba göz atarsanız, bir sonraki kokteyl partinizde çoğu insandan çok daha üstün olursunuz.

• "Sertlik vs. Rastgelelik" (Noam Nisan ile birlikte yazılmıştır)
  Diğer bulguların yanı sıra, bu makale yeni bir tür sözde rastgele oluşturucuyu tanıttı ve rastgeleleştirilmiş algoritmaların etkili deterministik simülasyonunun önceden bilinenden çok daha zayıf varsayımlar altında mümkün olduğunu kanıtladı.

• "EXTIME'ın Yayınlanabilir Kanıtları Olmadığı sürece BPP Alt Üstel Zaman Simülasyonlarına Sahiptir" (László Babai, Lance Fortnow ve Noam Nisan ile birlikte yazılmıştır)
  Bu makale, sınırlı hata olasılıklı polinom zamanının (BPP) daha zayıf varsayımlar altında sonsuz sayıda giriş uzunluğu için üstel altı zamanda simüle edilebilir.

• "P=BPP, eğer E Üstel Devreler Gerektiriyorsa: XOR Lemmasını Rastgelelikten Arındırmak" (Russell Impagliazzo ile birlikte yazılmıştır)
  Bu makale, esasen optimal sertlik ve rastgelelik ödünleşimlerine sahip daha güçlü bir sözde rastgele oluşturucuyu tanıtmaktadır.

67 yaşındaki Wigderson için şaşırtıcı bağlantıları ortaya çıkarmanın zevki, erken yaşlardan beri itici bir dürtüydü.

Wigderson, "Matematiği erken çocukluktan beri her zaman sevdim" dedi. "Babam bulmaca ve benzeri şeylere ilgi duyuyordu."

Wigderson, İsrail Technion'dan (Teknoloji Enstitüsü) mezun oldu ve Princeton Üniversitesi'nden bilgisayar bilimleri alanında yüksek lisans ve doktora dereceleri aldı. Technion'dan fahri doktora unvanını alan Wigderson'ın geçen yıl yaptığı kabul konuşmasında deneyimleri hakkında etkileyici bir konuşma yapıldı.

Wigderson, ilgisini çeken şey hakkında "Hesaplamalı modelleri resmileştirmeyi gerçekten önemsiyorum" dedi, "mesela, bazı kriptografik protokoller güvenli mi veya bazı algoritmaların çalışma süresi falan mı?

"Bu temel kavramı ele alması ama aslında bir matematik alanı olması benim için çok değerli."

Wigderson, en çok gurur duyduğu başarıların arasında, bilgilerin gizli tutulabileceği ancak yine de iki karşı tarafın bir anlaşmaya varabileceği "sıfır bilgi kanıtları" olarak adlandırılan çalışmaları geliştirmesi olduğunu söyledi. "Diyelim ki ben bir şey biliyorum, seçimi kimin kazanacağını biliyorum ve siz bana inanmıyorsunuz ve ben sizi (gerçekten inandığıma) ikna etmeye çalışıyorum. Size söylemeden sizi ikna etmenin bir yolu var. zaten bilmediğin bir şey."

Aslında bu tür bir durum, her bir tarafın kendi özel anahtarını sakladığı ancak diğerini örneğin yetkili bir şekilde bir elektronik sözleşme imzaladığına ikna edebildiği açık anahtar şifrelemesinin köküdür. Wigderson bu tür sıfır bilgi kanıtlarıyla ilgili olarak "Bu tamamen paradoksal bir fikir" dedi. "Bu, böyle bir şeyin var olabileceğini düşünmek aklınızı başınızdan alacak türden bir şey."

Wigderson'un zekası, zevk ile altta yatan önemi keskin bir şekilde dengeliyor. Örneğin hangi sorunların açıkça zor olduğu sorusu toplum için büyük öneme sahiptir.

1970'lerde formüle edildiği gibi, "P=NP mi?" ifadesi, çözümü doğrulanabilecek bir problemin sonuçta polinom-zaman denklemi ile de çözülüp çözülemeyeceğini soruyor; yani verimli bir şekilde çözülüyor. Eğer öyleyse, o zaman dünyanın çözülmesi zor gibi görünen sorunlarından bazılarını pratik zaman aralıklarında çözecek bir bilgisayar üretilebilir.

P=NP'den Wigderson, "Bu şimdiye kadar sorulan en temel entelektüel sorulardan biri" dedi. Alanında fikir birliği olan kişisel varsayımı, P'nin NP'ye eşit olmadığı yönündedir; bu, bazı sorunların verimli bir şekilde çözülmenin ötesinde olduğu anlamına gelir.

Wigderson, "Herkes yanılıyorsa ve P, NP'ye eşitse, bunun şaşırtıcı sonuçları olur" dedi. "Neredeyse çözmek istediğiniz herhangi bir sorunu etkili bir şekilde çözebilirsiniz; her şeyi; kanseri tedavi edebilirsiniz."

Ancak Wigderson, "Eğer P, NP'ye eşit değilse, ulaşamayacağımız şeylerin sonuçları oldukça önemlidir" dedi. Öncelikle bu, yaratıcılık gibi insan düşüncesinin bazı unsurlarının bilgisayarların erişiminin ötesinde olabileceği anlamına gelir, çünkü buluşsal yöntemleri, örneğin sanatsal yaratımda kullanılan insani algıyı verimli bir şekilde simüle etmenin bir yolu yoktur. .

Ancak başka bir anlamda bardağın yarısı dolu: Wigderson, eğer NP problemleri verimli bir şekilde çözülemezse, bu, modern ekonominin tüm temeli olan kriptografinin kırılmaya karşı güvende olduğu anlamına geliyor, dedi.

P'nin NP'ye eşit olup olmadığı açık bir sorudur. Wigderson, "Hayatım boyunca birisinin bunu kanıtlayacağını umuyordum ama artık bundan şüpheliyim" dedi.

Kuantum bilgisayarı da bu çıkmaza kolay bir cevap değil. Wigderson, "Bir kuantum bilgisayarı düşünün: bu mevcut değil" dedi. Her ne kadar IBM, Google ve diğerleri tarafından yoğun bir şekilde teorileştirilse de, "Var olup olmayacağını bilmiyoruz".

Eğer P=NP açık bir sorunsa, o anın sorusu da şu: "Yapay genel zeka" makineleri de dahil olmak üzere yapay zeka, insan düşüncesine eşit olmak için ne yapabilir veya yapmayabilir? Elbette, evrendeki her şeyin hesaplandığı fikri, yapay zekanın bir miktar insan yeteneği elde edebilmesi gerektiğini ima ediyor.

Wigderson'un görüşü, "Biz karbonuz, onlar da silikon, dolayısıyla malzeme farklı, ancak zorluklar operasyonel düzeyde değil, psikolojik düzeyde." Wigderson, yapay zekanın "daha önce nasıl çözeceğimizi bilmediğimiz birçok sorunu çözebileceğini" zaten gösterdiğini söyledi. Teorem kanıtlama ve benzeri konularda "bu cihazları işbirlikçi olarak kullanmaya başlayan bazı önde gelen matematikçileri" tanıyor.

"Benim için daha ilginç olan ne yapamadıkları" dedi. "Bu tür bir bilgisayarın sınırları nelerdir?" Bu sınırlardan biri, yapay zeka modellerini bazı problemlere yönelik eğitmek için gereken verilerin göreceli olarak az olmasıdır.

"Örneğin, görelilik veya Maxwell [Maxwell Denklemleri] gibi yeni bir matematik teorisi tasarlamak -- bunlar için çok daha az örnek var, değil mi? Dolayısıyla bu tür teorik atılımların bu makineler için daha zor olacağını düşünüyorum çünkü çok fazla veri yok."

P'nin NP'ye eşit olup olmamasının birçok sonucu açısından Wigderson, yeni neslin yol göstermesine izin vermekle yetiniyor.

"Enstitüdeki doktora sonrası araştırmacılarla eğleniyorum ve hepsi muhteşem, bazılarıyla işbirliği yapıyorum ve sadece gençlerden bir şeyler öğreniyorum" dedi. "Öğrenmenizi sağlayan gençlerle çevrili bu durumda olmak çok güzel."