簡介
想像一下，您正在尋求了解計算的本質。你身處荒野深處，遠離任何道路， 深不可測的 消息 被雕刻在你周圍的樹幹上——BPP，AC0[米]，Σ2P、YACC 和其他數百個。這些字形試圖告訴你一些事情，但要從哪裡開始呢？你甚至無法讓它們全部保持直線。
很少有研究人員能做到這一點 羅素（Russell Impagliazzo） 打破這看似混亂的局面。 40 年來，Impagliazzo 一直致力於計算複雜性理論的前沿，研究不同問題的內在難度。該領域最著名的開放性問題稱為 P 與 NP 問題，它詢問許多看似困難的計算問題是否實際上很容易——只要使用正確的演算法。答案將對科學和現代密碼學的安全產生深遠的影響。
在 1980 世紀 1990 年代和 XNUMX 年代，Impagliazzo 在統一 密碼學的理論基礎。 1995 年，他在一篇標誌性論文中闡明了這些新發展的重要性，該論文以以下語言重新闡述了 P 與 NP 的可能解決方案以及一些相關問題： 五個假設的世界 我們可能會住在被異想天開地稱為 Algorithmica、Heuristica、Pessiland、Minicrypt 和 Cryptomania 的地方。因帕利亞佐的五個世界啟發了一代研究人員，他們繼續指導蓬勃發展的子領域的研究 元複雜性.
這些並不是他唯一夢想的世界。 Impagliazo 一生都是《龍與地下城》等桌上角色扮演遊戲的愛好者，他樂於發明 新規則 以及可供探索的新設定。同樣的頑皮精神也為他 30 年的即興喜劇創作注入了活力。
Impagliazzo 也做了基礎工作，闡明了隨機性在計算中的基本作用。在 1970 世紀 XNUMX 年代末，電腦科學家發現隨機性有時可以 改進演算法 解決本質上的確定性問題——這項違反直覺的發現多年來一直困擾著研究人員。因帕利亞佐與複雜性理論家的合作 阿維威德森 和 1990 世紀 XNUMX 年代的其他研究人員表明，如果某些計算問題確實從根本上來說是困難的，那麼它 總是有可能 將使用隨機性的演算法轉換為確定性演算法。相反，證明可以從任何演算法中消除隨機性 也將證明 確實存在困難的問題。
廣達 與 Impagliazzo 討論了難題和難題之間的區別、諮詢神諭以及即興喜劇的數學課程。為了清晰起見，採訪內容已經過精簡和編輯。
簡介
什麼時候第一次對數學產生興趣？
在我真正知道數學是什麼之前，我就對數學感興趣了。三年級時，我的數學成績開始下滑，因為我們要記得乘法表，但我拒絕了。我媽媽說：“但是拉塞爾，你喜歡數學，為什麼不這樣做呢？”我說：「那不是數學，那是記憶。真正的數學不涉及記憶。”那時我學到的只是算術，所以我不確定我從哪裡得到數學是關於抽象概念的概念。
計算機科學呢？該領域的某些部分非常抽象，但它們並不是大多數人第一次遇到的。
高中時，我學過 BASIC 程式設計課程，但完成任何事情都非常困難。這些程序必須轉移到紙帶上，紙帶必須通過這台非常舊的計算機運行，該計算機經常發生故障並將您的紙張撕成兩半。所以我認為計算機科學非常枯燥。
我本來打算學習邏輯。但是，當您嘗試實際形式化許多概念時，它們涉及計算，尤其是計算的限制。諸如「我們如何知道數學中的事物是真的？」之類的問題以及“我們如何理解做數學的困難？”導致了理論計算機科學，尤其是複雜性理論。
您最著名的作品探討了密碼學和計算複雜性理論之間的關聯。為什麼這兩個領域相關？
當您設定加密系統時，您需要區分合法使用者（您想要授予存取權限的人）和其他人。計算困難的問題為我們提供了一種根據這些群體所知道的知識來區分這些群體的方法。但如果你想知道一個問題的答案來區分兩組人，你就不能只用任何困難的問題——你需要一個困難的謎題。
簡介
問題和謎題有什麼差別？
一般來說，提出問題的人可能不知道答案。謎題是在設計時考慮到答案的問題。那我們為什麼需要拼圖呢？因為我們需要能夠確定一個被認為解決了這個問題的人是否真的解決了這個問題。在日常生活中，我們使用拼圖來娛樂，但我們也在課堂上使用它們來測試人們是否理解材料。這就是密碼學中發生的情況：我們使用謎題來測試某人的知識。
這五個世界的差別在於他們如何回答「有困難的問題嗎？」的問題。和“有困難的謎題嗎？”
這些不同的答案如何發揮作用？
在第一個世界 Algorithmica 中，沒有什麼問題是困難的。你不必知道別人是如何設計你的問題的：你總是可以解決它。 Heuristica 說的是：“好吧，也許有些問題很難。”然後我們到達佩西蘭，那裡的許多問題都很困難，但大多數謎題並不困難。幾乎任何我知道解決方案的問題，你也能解決。所有這些都不利於密碼學。
在 Minicrypt 中，我可以創建我知道如何解決的謎題，但對您來說仍然具有挑戰性。最後，在《Cryptomania》中，兩個人可以站在竊聽者可以聽到的公共場所，一起創造一個對竊聽者來說仍然很難的謎題。
是什麼促使你寫五個世界的論文？
當時，人們知道 P 與 NP 問題的不同答案將對我們能夠解決什麼樣的問題以及我們能夠期望什麼樣的安全性產生很大的影響，但是不同形式的容易性和 NP 形式之間的質的區別硬度不太清楚。
幾年前有一篇非常有洞察力的論文，其中使用許多相互關聯的問題和大約 20 個可能的答案來闡述這些差異。我想寫五個世界論文的原因之一是我們在這幾年裡取得了巨大的進展。要為 20 個可能的世界找到名稱是很困難的。
簡介
那麼為什麼要這樣定義它，將其視為具有古怪名稱的不同世界呢？
我同意為一次會議寫這篇論文。我熬夜試圖弄清楚我要說什麼，凌晨 1 點左右的某個時候，不同世界的框架似乎是個好主意。第二天早上我讀到它，它看起來仍然是一個不錯的想法——這是一種展示這些想法將如何真正影響世界的方式，而無需陷入定量細節。這篇論文最讓我高興的是，我從從事複雜性研究的人那裡聽說，這篇論文讓他們作為本科生對該領域產生了興趣。
研究人員是否排除了五個可能世界中的任何一個？
我們實際上正在添加更多內容——人們已經開始談論 混淆烏托邦 作為一個擁有更強大的加密工具的世界。令人有點沮喪的是，我們在 1980 世紀 XNUMX 年代末取得瞭如此大的進步，但從那時起就沒有消除任何世界。但另一方面，我們對世界之間的連結了解更多，並且對 更清晰的圖片 每個世界都會是什麼樣子。
假設世界在複雜性理論中還發揮另一個作用，即在假設「神諭」存在的證明中發揮作用。那麼，首先，什麼是預言機？
想像一下，有人建造了一個巧妙的設備，可以解決某些問題，而我們不知道解決該問題的演算法。這就是神諭。如果我們有這樣一個神奇的設備，並將其放入計算機中，它可能會改變可計算和不可計算之間的界限。
簡介
研究人員認為這些魔盒真的存在嗎？
不，它們可能不存在。早期，甲骨文的結果有些爭議，因為它們過於假設。但它們非常有啟發性的一種方式是，當使用預言機來模擬理想情況時。假設你試圖證明 A 並不一定意味著 B。你從具有最極端 A 的設定開始，並表明這仍然不足以保證 B。如果你可以證明即使所有的可能性都是對你有利，你仍然無法證明某件事，這是非常有力的證據，顯示它很難證明。
您還發現了計算難度和隨機性之間的關聯。這種連結如何運作？
這實際上是一種說法，如果你不理解某件事，那麼它可能看起來是隨機的。假設我說我正在考慮一到一千之間的數字。如果我隨機選一個數字，你猜到的機會是千分之一。如果我問——按照巨蟒劇團的說法——“歐洲燕子的平均空速是多少？”你也有同樣的機會。它可能每小時行駛超過一英里，也可能不會超過每小時一千英里。
這實際上並不是隨機的——這是一個可以確定地回答的問題。我們可以測量所有飛來飛去的燕子，但在資源有限的情況下很難確定，例如沒有測量燕子速度的預算，也沒有無限供應的燕子。
因此，我們的見解是，我們不知道其解決方案的難題可以提供看起來隨機的「偽隨機」數字的來源。
簡介
說到巨蟒劇團，我知道你已經從事即興喜劇很久了——你是怎麼開始的？
1991 年，我開始在聖地亞哥擔任助理教授。大約在 94 年左右，我想，“我在系外真的沒有太多生活。”所以我得到了免費的周報，並瀏覽了俱樂部和活動的清單。我排除了除了即興喜劇之外的一切——我認為至少我可以勝任。我在初級班認識了我的妻子。
她怎麼想？
她說我真的很糟糕。當你是邏輯學家時，你接受的訓練就是始終思考每個單字的細微差別。你不想說一些不正確的話。即興表演的偉大之處在於它扭轉了這一點：重點不是說一些完美的話，而是快速彌補一些東西。這與我的餘生相反。
我現在的妻子休了一次課，一年後她回來時，我給她留下了深刻的印象。那是30年前的事了。我仍然在同一位老師的指導下上同一堂課。
即興創作是否改變了您的研究方式？
不要對你的每一個想法都吹毛求疵，這是一個很好的做法。這對於合作特別有幫助。當與其他人一起工作時，我常常這樣說：「但是這個想法行不通，原因如下。這實際上不是真的。”在即興表演中，你總是應該接受你的搭檔所說的話。我認為這是一個很好的態度，尤其是當你和學生一起做研究時：不要因為你知道他們所說的不正確而忽視他們所說的東西。有很多好的想法並不是 100% 正確。
簡介
像什麼？
當你試圖獲得對問題的直覺時，有幫助的一件事就是從一些簡化的假設開始。這些假設通常不正確，但它們可以幫助您制定路線圖。說：「如果我有一頭大象，我就可以翻山越嶺。當然，我沒有大象。但如果我這樣做的話，我會這樣做。”然後你意識到，「好吧，也許我不需要大象來完成這一步。騾子就好了。”
你對角色扮演遊戲的熱愛如何——這對你的工作有影響嗎？
它可能不會影響我所有的研究，但它確實影響了我的五個世界論文。我一直對奇幻和科幻小說很感興趣，並想出不同的可能世界——如果一切都不同的話，事情會是什麼樣子？
為什麼角色扮演遊戲是探索假設世界的一種引人注目的方式？
熱衷於推理小說的人總是會創造一些世界。托爾金因此而聞名，他擁有如此豐富的想像力，以至於他的世界實際上讓人感覺生活在其中。對於我們這些缺乏想像力的人來說，實現這一目標的最佳方法就是邀請人們進入你的環境，然後玩遊戲是這樣做的一種方法。現在這不僅僅是我的世界。它可能是按照我想像的方式開始的，但就像任何合作一樣，由於其他人的貢獻，它已經遠遠超出了這個範圍。
