Hesaplamanın doğasını anlama arayışında olduğunuzu hayal edin. Vahşi doğanın derinliklerindesin, her türlü yoldan uzaktasın ve esrarengiz mesajları etrafınızdaki ağaç gövdelerine oyulmuş — BPP, AC⁰[m], Σ₂P, YACC ve diğer yüzlerce kişi. Glifler sana bir şey anlatmaya çalışıyor ama nereden başlamalı? Hepsini doğru düzgün tutamıyorsun bile.

Çok az araştırmacı bu kadarını yaptı Russel İmpagliazzo Bu görünen kaosu ortadan kaldırmak için. 40 yıldır Impagliazzo, farklı problemlerin içsel zorluklarının incelenmesi olan hesaplamalı karmaşıklık teorisinin ön saflarında çalıştı. Bu alandaki en ünlü açık soru, P'ye karşı NP problemi olarak adlandırılan, görünüşte zor olan birçok hesaplama probleminin doğru algoritmayla gerçekten kolay olup olmadığını sorar. Bir cevabın bilim ve modern kriptografinin güvenliği açısından geniş kapsamlı sonuçları olacaktır.

1980'lerde ve 1990'larda Impagliazzo, Avrupa Birliği'nin birleştirilmesinde öncü bir rol oynadı. kriptografinin teorik temelleri. 1995 yılında, P'ye karşı NP'ye olası çözümleri ve bir avuç ilgili problemi yeniden formüle eden ikonik bir makalede bu yeni gelişmelerin önemini dile getirdi. beş varsayımsal dünya tuhaf bir şekilde Algorithmica, Heuristica, Pessiland, Minicrypt ve Cryptomania olarak adlandırılan bu yerde yaşayabiliriz. Impagliazzo'nun beş dünyası bir nesil araştırmacıya ilham kaynağı oldu ve gelişen alt alan araştırmalarına rehberlik etmeye devam ediyorlar. meta-karmaşıklık.

Ve onun hayalini kurduğu tek dünyalar bunlar değil. Impagliazzo, Dungeons and Dragons gibi masa üstü rol yapma oyunlarının ömür boyu tutkunu olmuştur ve icat etmekten büyük keyif almaktadır. yeni kurallar dizisi ve keşfedilecek yeni ayarlar. Aynı şakacı ruh, onun 30 yıllık doğaçlama komedi pratiğini de canlandırıyor.

Impagliazzo ayrıca hesaplamada rastgeleliğin temel rolünü aydınlatan temel çalışmalar yaptı. 1970'lerin sonlarında bilgisayar bilimciler rastgeleliğin bazen algoritmaları geliştirin doğası gereği deterministik problemleri çözmek için - yıllarca araştırmacıları şaşırtan mantığa aykırı bir bulgu. Impagliazzo'nun karmaşıklık teorisyeni ile çalışması Avi Wigderson ve diğer araştırmacılar 1990'larda bazı hesaplama problemlerinin gerçekten temelde zor olduğunu gösterdiler. her zaman mümkün Rastgeleliği kullanan algoritmaları deterministik algoritmalara dönüştürmek. Ve tam tersine, herhangi bir algoritmada rastgeleliğin ortadan kaldırılabileceğini kanıtlamak ayrıca kanıtlayacaktı gerçekten zor sorunların var olduğunu.

Kuantum Impagliazzo ile zor problemler ile zor bulmacalar arasındaki farklar, kahinlere danışma ve doğaçlama komedinin matematik dersleri hakkında konuştu. Röportaj, netlik sağlamak amacıyla kısaltıldı ve düzenlendi.

Matematiğe ilginiz ilk ne zaman başladı?

Matematiğin ne olduğunu gerçekten bilmeden önce bile matematiğe ilgim vardı. Üçüncü sınıfta çarpım tablosunu ezberlememiz gerektiği için matematik notlarım düşmeye başladı ve ben reddettim. Annem, “Ama Russell, matematiği seviyorsun, bunu neden yapmıyorsun?” dedi. Ben de dedim ki, “Bu matematik değil, bu ezberleme. Gerçek matematik ezberlemeyi gerektirmez.” O noktada öğrendiğim tek şey aritmetikti, dolayısıyla matematiğin soyut kavramlarla ilgili olduğu fikrini nereden edindiğimden emin değilim.

Peki ya bilgisayar bilimi? Alanın bazı kısımları oldukça soyuttur ancak çoğu insanın ilk karşılaştığı şey değildir.

Lisedeyken BASIC programlama dersi almıştım ama bir şeyler yapmak gerçekten zordu. Programların, sıklıkla arızalanan ve kağıdınızı ikiye bölen bu çok eski bilgisayar üzerinden çalıştırılması gereken kağıt bantlara aktarılması gerekiyordu. Bu yüzden bilgisayar biliminin son derece sıkıcı olduğunu düşündüm.

Mantık okumayı düşünüyordum. Ancak kavramların çoğu, onları gerçekten resmileştirmeye çalıştığınızda, hesaplamayı ve özellikle hesaplamanın sınırlarını içeriyordu. “Matematikteki şeylerin doğru olduğunu nasıl bilebiliriz?” gibi sorular ve “Matematik yapmanın zorluğunu nasıl anlarız?” teorik bilgisayar bilimine ve özellikle karmaşıklık teorisine yol açtı.

En ünlü çalışmalarınızdan bazıları kriptografi ile hesaplamalı karmaşıklık teorisi arasındaki bağlantıları araştırıyor. Bu iki alan neden birbiriyle ilişkili?

Bir şifreleme sistemi kurarken meşru kullanıcılar (erişim izni vermek istediğiniz kişiler) ile diğer herkes arasında ayrım yapmanız gerekir. Hesaplama açısından zor problemler bize bu grupları bildiklerine göre ayırmamız için bir yol sağlar. Ancak iki grup insanı ayırt etmenin bir yolu olarak bir sorunun cevabını bilmek istiyorsanız, herhangi bir zor problemi kullanamazsınız; zor bir bulmacaya ihtiyacınız vardır.

Bir problem ile bir bulmaca arasındaki fark nedir?

Genelde problemi ortaya atan kişi cevabı bilemeyebilir. Bulmaca, bir cevap düşünülerek tasarlanmış bir problemdir. Peki neden bir bulmacaya ihtiyacımız var? Çünkü bunu sözde çözen kişinin gerçekten çözüp çözmediğini tespit edebilmemiz gerekiyor. Günlük yaşamda bulmacaları eğlence için kullanırız, ancak aynı zamanda bunları sınıflarda insanların konuyu anlayıp anlamadığını test etmek için de kullanırız. Kriptografide olan budur: Birinin bilgisini test etmek için bulmacalar kullanırız.

Beş dünya arasındaki fark, "Zor problemler var mı?" ve "Zor bulmacalar var mı?"

Bu farklı cevaplar nasıl sonuçlanıyor?

Birinci dünya olan Algorithmica'da hiçbir sorun zor değildir. Birinin probleminizi nasıl tasarladığını bilmenize gerek yok: Onu her zaman çözebilirsiniz. Heuristica şöyle diyor: "Belki de birkaç sorun zordur." Sonra Pessiland'a varıyoruz, orada pek çok problem zor ama çoğu bulmaca öyle değil. Çözümünü bildiğim yerde uydurduğum neredeyse her sorunu sen de çözebileceksin. Bu dünyaların tümü kriptografi için kötüdür.

Minicrypt'te, hala sizin için gerçekten zorlayıcı olan, nasıl çözüleceğini bildiğim bulmacalar oluşturabilirim. Ve son olarak, Cryptomania, iki kişinin, kulak misafiri olan kişinin duyabileceği halka açık bir yerde durup, kulak misafiri için hala zor olan bir bulmacayı birlikte oluşturabildiği bir dünyadır.

Beş dünya makalesini yazmaya sizi motive eden şey neydi?

O zamanlar, P'ye karşı NP sorusuna verilen farklı yanıtların, ne tür sorunları çözebileceğimiz ve aynı zamanda ne tür bir güvenlik umabileceğimiz üzerinde büyük bir etkiye sahip olacağı biliniyordu; ancak farklı kolaylık ve kolaylık biçimleri arasındaki niteliksel ayrımlar, sertlik gerçekten net değildi.

Sadece birkaç yıl önce, birbiriyle ilişkili birçok soruyu ve 20'ye yakın olası cevabı kullanarak ayrımları ortaya koyan çok aydınlatıcı bir makale vardı. Beş dünya makalesini yazmak istememin bir nedeni de bu birkaç yılda çok büyük ilerleme kaydetmiş olmamızdı. 20 olası dünya için isim bulmak zor olurdu.

Öyleyse neden bunu ilginç adlara sahip farklı dünyalar olarak çerçeveleyesiniz ki?

Bu makaleyi bir konferans için yazmayı kabul etmiştim. Gece geç saatlere kadar ne söyleyeceğimi bulmaya çalışıyordum ve saat 1 civarında farklı dünyaların çerçevelenmesi iyi bir fikir gibi göründü. Ertesi sabah bunu okudum ve yine de iyi bir fikir gibi göründü; niceliksel ayrıntılara takılmadan bu fikirlerin aslında dünyayı nasıl etkileyeceğini göstermenin bir yoluydu. Bu makaleyle ilgili beni en çok mutlu eden şey, karmaşık konularda araştırma yapan insanlardan, lisans öğrencileri olarak bu alana ilgi duymalarını sağlayan makalenin bu olduğunu duymamdır.

Araştırmacılar olası beş dünyadan herhangi birini eledi mi?

Aslında daha fazlasını ekliyoruz; insanlar bunun hakkında konuşmaya başladı Şaşkınlık daha da güçlü şifreleme araçlarının olduğu bir dünya olarak. 1980'lerin sonlarında bu kadar ilerleme kaydetmiş olmamız ve o zamandan bu yana hiçbir dünyayı elememiş olmamız biraz moral bozucu. Ancak öte yandan, dünyalar arasındaki bağlantılar hakkında çok daha fazla şey biliyoruz ve çok daha net resim her bir dünyanın neye benzeyeceğine dair.

Varsayımsal dünyalar karmaşıklık teorisinde, "kehanetlerin" varlığını varsayan kanıtlarda da başka bir rol oynar. Peki, öncelikle kehanet tam olarak nedir?

Birisinin, biz o sorunu çözmeye yönelik bir algoritma bilmeden, bazı sorunları çözebilecek ustaca bir cihaz yaptığını hayal edin. Kehanet budur. Eğer böyle mucizevi bir cihazımız olsaydı ve onu bilgisayarlarımıza koysaydık, hesaplanabilen ile hesaplanamayan arasındaki çizgiyi değiştirebilirdi.

Araştırmacılar bu sihirli kutuların gerçekten var olabileceğini düşünüyor mu?

Hayır, muhtemelen mevcut değiller. Başlangıçta, kehanet sonuçları oldukça varsayımsal olduğundan biraz tartışmalıydı. Ancak bunların çok aydınlatıcı olabilmesinin bir yolu, kehanetin ideal bir durumu modellemek için kullanılmasıdır. Diyelim ki A'nın mutlaka B'yi ima etmediğini göstermeye çalışıyorsunuz. En uç A'ya sahip olduğunuz ortamla başlıyorsunuz ve bunun B'yi garanti etmek için hala yeterli olmadığını gösteriyorsunuz. Tüm olasılıklar aynı olsa bile bunu gösterebiliyorsanız sizin lehinize, hala bir şeyi kanıtlayamıyorsunuz, bu, kanıtlamanın zor olacağına dair gerçekten güçlü bir kanıt.

Ayrıca hesaplama sertliği ile rastgelelik arasındaki bağlantıları da keşfettiniz. Bu bağlantı nasıl çalışıyor?

Bu aslında bir şeyi anlamıyorsanız bunun rastgele görünebileceğini söylemenin bir yolu. Diyelim ki bir ile bin arasında bir sayı düşündüğümü söylüyorum. Eğer sayıyı rastgele seçersem, tahmin etme şansın binde birdir. Monty Python'u takip ederek, "Saatte mil cinsinden, bir Avrupalı ​​kırlangıcın ortalama hava hızı nedir?" diye sorarsam. hemen hemen aynı şansa sahipsiniz. Muhtemelen saatte bir milden fazla gidiyor ve muhtemelen saatte bin milden fazla gitmiyor.

Bu aslında rastgele değil; deterministik olarak yanıtlanabilir bir soru. Etrafta uçuşan tüm kırlangıçları ölçebiliyoruz ancak sınırlı kaynaklarla bunu belirlemek biraz zor; örneğin yutkunma hızlarını ölçecek bir bütçeye sahip olmamak ve sonsuz miktarda kırlangıç ​​kaynağına sahip olmamak gibi.

Dolayısıyla, çözümlerini bilmediğimiz zor problemlerin, rastgele görünen "sahte rastgele" sayıların kaynağını sağlayabildiği içgörüdür.

Monty Python'dan bahsetmişken, uzun zamandır doğaçlama komedi yaptığınızı biliyorum; nasıl başladınız?

1991 yılında San Diego'da yardımcı doçent olarak başladım. 94 civarında şöyle düşündüm: "Bölüm dışında pek bir hayatım yok." Böylece haftalık ücretsiz gazeteyi aldım ve kulüp ve aktivite listesine göz attım. Doğaçlama komedi dışındaki her şeyi eledim; en azından bunda başarılı olabileceğimin makul olduğunu düşündüm. Eşimle o başlangıç ​​sınıfında tanıştım.

Ne düşünüyordu?

Gerçekten çok kötü olduğumu söylüyor. Mantıkçı olduğunuzda her zaman her kelimenin ince ayrıntılarını düşünmek üzere eğitilirsiniz. Yanlış bir şey söylemek istemezsin. Doğaçlama harikadır çünkü bunu tersine çevirir: Önemli olan mükemmel bir şey söylemek değil, hızlı bir şekilde bir şeyler uydurmaktır. Hayatımın geri kalanının tam tersi oldu.

Şimdiki eşim derslere ara verdi ve bir yıl sonra geri döndüğünde onu etkilemeyi başardım. Bu 30 yıl önceydi. Halen aynı hocadan aynı dersi alıyorum.

Doğaçlama yapmak araştırmanıza yaklaşma şeklinizi değiştirdi mi?

Sahip olduğunuz her düşünceye karşı aşırı eleştirel olmamak iyi bir uygulamadır. Bu özellikle işbirliklerinde faydalıdır. Başkalarıyla iş yaparken şöyle şeyler söylerdim: “Ama bu fikir şu nedenden dolayı işe yaramayacak. Bu kelimenin tam anlamıyla doğru değil. Doğaçlamada partnerinizin söylediklerini her zaman kabul etmeniz gerekir. Ve bence bu, sahip olunması gereken iyi bir tutum, özellikle de öğrencilerle araştırma yaparken: Söyledikleri bir şeyi sırf yanlış olduğunu bildiğiniz için göz ardı etmeyin. %100 doğru olmayan pek çok iyi fikir var.

Ne gibi?

Bir problem için sezgiye ulaşmaya çalıştığınızda, bazı basitleştirici varsayımlarla başlamanıza yardımcı olacak şeylerden biri de budur. Bu varsayımlar genellikle doğru değildir ancak bir yol haritası çıkarmanıza yardımcı olabilirler. De ki: “Filim olsaydı dağları aşabilirdim. Tabii ki bir filim yok. Ama eğer yapsaydım, işte bunu nasıl yapardım. Ve sonra şunu fark edersiniz: “Belki de bu adım için bir file ihtiyacım yoktur. Bir katır iyi olurdu.”

Peki ya rol yapma oyunlarına olan sevginiz, çalışmalarınızı hiç etkiledi mi?

Bütün araştırmamı etkilememiş olabilir ama beş dünya makalemi kesinlikle etkiledi. Fantastik ve bilim kurguya ve farklı olası dünyalar bulmaya her zaman genel bir ilgim olmuştur; her şey farklı olsaydı her şey nasıl olurdu?

Rol yapma oyunları neden varsayımsal dünyaları keşfetmenin bu kadar ilgi çekici bir yoludur?

Spekülatif kurguyla ilgilenen insanlar her zaman dünyalar icat etmişlerdir. Tolkien en çok bu özelliğiyle ünlüdür ve o kadar büyük bir hayal gücüne sahipti ki, sanki kendi dünyası yaşanmış gibi hissediyordu. Onun kadar hayal gücü olmayan bizler için bunu başarmanın en iyi yolu, insanları ortamınıza davet etmek ve bir oyun oynamaktır. bunu yapmanın bir yoludur. Artık sadece benim dünyam değil. Hayal ettiğim gibi başlamış olabilir ama her işbirliğinde olduğu gibi, herkesin katkıları sayesinde bunun çok ötesine geçti.