あなたが計算の性質そのものを理解しようとしているところを想像してみてください。あなたは荒野の奥深く、道から遠く離れたところにいます、そして 不可解な メッセージ あなたの周りの木の幹に刻まれています - BPP、AC⁰[m]、Σ₂P、YACC、その他数百社。グリフは何かを伝えようとしていますが、どこから始めればよいでしょうか?それらをすべてまっすぐに保つことさえできません。

これほど多くの研究を行った研究者はほとんどいません ラッセルインパリアッツォ この一見混沌とした状況を切り開くために。 Impagliazzo は 40 年間にわたり、さまざまな問題の本質的な難しさの研究である計算複雑性理論の最前線で働いてきました。この分野で最も有名な未解決の質問は、P 対 NP 問題と呼ばれ、一見難しそうに見える多くの計算問題が、適切なアルゴリズムを使用すれば実際には簡単であるかどうかを問うものです。その答えは、科学と現代の暗号のセキュリティに広範囲に影響を与えるでしょう。

1980 年代と 1990 年代、インパリアッツォは国家の統一において主導的な役割を果たしました。 暗号の理論的基礎。 1995 年、彼は、P 対 NP およびいくつかの関連問題に対する考えられる解決策を言語で再定式化した象徴的な論文の中で、これらの新たな発展の重要性を明確に述べました。 5つの仮想世界 私たちは、気まぐれに「アルゴリズム」、「ヒューリスティカ」、「ペシランド」、「ミニクリプト」、「クリプトマニア」と呼ばれる存在として生きているかもしれません。インパリアッツォの 5 つの世界は、何世代もの研究者にインスピレーションを与え、現在も繁栄している下位分野の研究を導き続けています。 メタ複雑性.

そして、彼が夢見た世界はこれだけではありません。インパリアッツォは、ダンジョンズ アンド ドラゴンズのような卓上ロールプレイング ゲームの生涯にわたる愛好家であり、発明することに喜びを感じています。 新しいルールセット 新しい設定を探索することもできます。同じ遊び心のある精神が、彼の 30 年間にわたる即興コメディーの実践に活力を与えています。

Impagliazzo は、計算におけるランダム性の基本的な役割を解明する基礎的な研究も行いました。 1970 年代後半、コンピューター科学者は、ランダム性が時々起こることを発見しました。 アルゴリズムを改善する 本質的に決定論的な問題を解決するために、これは研究者を長年困惑させてきた直観に反する発見です。 Impagliazzo と複雑理論家との共同研究 アビ・ウィグダーソン および 1990 年代の他の研究者は、特定の計算問題が本当に根本的に難しい場合、それは問題であることを示しました。 いつでも可能 ランダム性を使用するアルゴリズムを決定論的なアルゴリズムに変換します。逆に、任意のアルゴリズムからランダム性を排除できることを証明する も証明されるだろう 本当に難しい問題が存在するということ。

クアンタ 難しい問題と難しいパズルの違い、神託の相談、そして即興コメディの数学的教訓についてインパリアッツォに語った。インタビューはわかりやすくするために要約および編集されています。

初めて数学に興味を持ったのはいつですか?

私は数学が何であるかを理解する前から数学に興味がありました。 3年生になると、九九を暗記することになっていたので、数学の成績が下がり始めましたが、私はそれを拒否しました。母は「でもラッセル、あなたは数学が好きなのに、なぜこれをやらないの？」と言いました。そして私は言いました、「それは数学ではありません、それは暗記です。」本当の数学には暗記は必要ありません。」その時点で私が学んだのは算術だけだったので、数学は抽象的な概念に関するものであるという概念をどこから得たのかわかりません。

コンピューターサイエンスについてはどうですか?この分野の一部は非常に抽象的ですが、ほとんどの人が最初に遭遇するものではありません。

高校のとき、BASICのプログラミングコースを受講していましたが、何をするにも本当に難しかったです。プログラムは紙テープに転送する必要があり、この非常に古いコンピューターで実行する必要があり、頻繁に誤動作して紙が真っ二つになってしまいました。そのため、コンピューターサイエンスは恐ろしく鈍いものだと思っていました。

私は論理学を勉強するつもりでした。しかし、多くの概念を実際に形式化しようとすると、計算、特に計算の制限が含まれます。 「数学の事柄が真実であることをどのようにして知ることができますか?」のような質問。 「数学を行うことの難しさをどうやって理解すればよいでしょうか?」理論的なコンピューターサイエンス、特に複雑さの理論につながりました。

あなたの最も有名な著作には、暗号化と計算複雑性理論の関係を調査したものがあります。なぜこれら 2 つの分野に関連があるのでしょうか?

暗号化システムを設定するときは、正当なユーザー (アクセスを許可したいユーザー) とそれ以外のユーザーを区別する必要があります。計算上難しい問題により、これらのグループが知っていることに基づいてこれらのグループを区別する方法が得られます。しかし、2 つのグループの人々を区別する方法として問題の答えを知りたい場合は、どんな難しい問題でも使用することはできません。難しいパズルが必要です。

問題とパズルの違いは何ですか?

一般に、問題を提起する人は答えを知らない可能性があります。パズルとは、答えを念頭に置いて設計された問題です。では、なぜパズルが必要なのでしょうか?なぜなら、問題を解決したと思われる人物が実際に解決したかどうかを判断できる必要があるからです。私たちは日常生活でパズルを娯楽として使用しますが、教室でも人々が内容を理解したかどうかをテストするために使用します。これが暗号化で起こっていることです。私たちはパズルを使って誰かの知識をテストしています。

5 つの世界の違いは、「難しい問題はありますか?」という質問にどう答えるかです。 「難しいパズルはありますか？」

それらの異なる答えはどのように展開されるのでしょうか?

最初の世界、アルゴリズミカでは、難しい問題はありません。誰かがあなたの問題をどのように設計したかを知る必要はありません。それはいつでも解決できます。 Heuristica は、「まあ、いくつかの問題は難しいかもしれません」と言っています。次に、ペシランドに到着します。そこでは多くの問題が難しいですが、ほとんどのパズルは難しくありません。私が解決策を知っている場合、私が考え出したほとんどすべての問題は、あなたにも解決できるでしょう。これらの世界はすべて、暗号化にとって好ましくありません。

Minicrypt では、私が解き方を知っていても、あなたにとっては非常に難しいパズルを作成できます。そして最後に、クリプトマニアは、盗聴者に聞こえる公共の場所に立って、盗聴者にとっては依然として難しいパズルを一緒に作成できる世界です。

五つの世界に関する論文を執筆した動機は何ですか?

当時、P 対 NP の質問に対する異なる答えが、どのような種類の問題を解決できるか、またどのような種類のセキュリティを期待できるかに大きな影響を与えることが知られていましたが、さまざまな形式の容易さと、硬さはあまり明確ではありませんでした。

ほんの数年前に、相互に関連する多くの質問と 20 個ほどの答えを使用して区別を説明した、非常に洞察力に富んだ論文がありました。私が五つの世界に関する論文を書こうと思った理由の 20 つは、この数年間で私たちが大きな進歩を遂げたからです。 XNUMX もの可能な世界の名前を見つけるのは大変だっただろう。

では、なぜ風変わりな名前を持つ異なる世界としてこのように枠組みを設定するのでしょうか?

私は会議のためにこの論文を書くことに同意しました。私は何を言おうかと考えて夜遅くまで起きていて、午前1時頃、さまざまな世界を構成するのが良いアイデアのように思えました。そして翌朝それを読んだのですが、それでもまだOKなアイデアのように思えました。定量的な詳細に囚われることなく、これらのアイデアが実際に世界にどのような影響を与えるかを示す方法でした。この論文で一番うれしいのは、複雑系の研究をしている人たちから、この論文が学部生のときにこの分野に興味を持ったきっかけになったと聞いたことです。

研究者は、可能性のある 5 つの世界のいずれかを除外しましたか?

実際にはさらに追加しています - 人々は次のように話し始めています オブフストピア さらに強力な暗号化ツールの世界として。私たちが 1980 年代後半にこれほど大きな進歩を遂げたのに、それ以来どのワールドも削除されていないのは少し憂鬱です。しかしその一方で、私たちは世界間のつながりについてより多くのことを知っており、 より鮮明な画像 それぞれの世界がどのように見えるか。

仮説の世界は、複雑性理論、つまり「神託」の存在を前提とした証明においても別の役割を果たします。それではまず、オラクルとは一体何でしょうか？

私たちが問題を解決するためのアルゴリズムを知らなくても、誰かが問題を解決できる独創的なデバイスを構築したと想像してください。それがオラクルです。もし私たちがそのような奇跡的なデバイスを持っていて、それを私たちのコンピューターの中に入れたら、計算できるものと計算できないものの間の境界線が変わる可能性があります。

研究者はこれらの魔法の箱が実際に存在する可能性があると考えていますか?

いや、おそらく存在しないだろう。オラクルの結果は非常に仮説的なものであるため、初期の頃は多少の物議を醸しました。しかし、それらが非常に啓発的になる方法の 1 つは、神託を理想的な状況をモデル化するために使用する場合です。 A が必ずしも B を暗示しているわけではないことを示そうとしているとします。最も極端な A が得られる設定から始めて、それが B を保証するにはまだ十分ではないことを示します。すべてのオッズが正しい場合でも、それを示すことができれば、あなたにとって有利なことは、あなたがまだ何かを証明できないということです。それは、証明するのが難しいことを示す強力な証拠です。

また、計算の難易度とランダム性との関連性も発見しました。その接続はどのように機能するのでしょうか?

これは、何かを理解していないと、それはでたらめに見えるかもしれないということを意味します。 1 から 1,000 までの数字を考えているとします。私がランダムに数字を選んだ場合、それを推測できる確率は 1000 分の 1 です。そして、モンティ・パイソンに倣って、私が「ヨーロッパのツバメの平均対気速度は時速マイルでどのくらいですか?」と尋ねたら、あなたにもほぼ同じチャンスがあります。おそらく時速 1 マイルを超えますが、おそらく時速 1,000 マイルを超えることはありません。

これは実際にはランダムではなく、決定論的に答えられる質問です。飛び回っているすべてのツバメを測定することもできますが、ツバメの速度を測定するための予算がない、ツバメが無限に供給されるわけではないなど、リソースが限られている中で判断するのは難しいです。

したがって、解決策がわからない難しい問題は、ランダムに見える「疑似乱数」のソースを提供する可能性があるという洞察が得られます。

モンティ・パイソンと言えば、あなたは長い間即興コメディをやっていると思いますが、どのようにして始めたのですか？

私は 1991 年にサンディエゴで助教授として働き始めました。そして 94 年頃、「学部以外の生活は本当につまらない」と思いました。そこで私は週刊フリーペーパーを手に入れ、クラブや活動のリストに目を通しました。私は即興コメディ以外のすべてを排除しました。少なくとも私はそれを大丈夫だと考えました。私はその初級クラスで妻と出会いました。

彼女はどう思いましたか？

彼女は私が本当にひどかったと言います。論理学者になると、すべての単語のニュアンスを常に考えるように訓練されます。間違ったことを言いたくありません。即興は、それを逆転させるという点で優れています。重要なのは、完璧なことを言うことではなく、何かを素早く作り上げることです。それは私の残りの人生とは真逆でした。

現在の妻はクラスを休みましたが、30 年後に戻ってきたとき、私は彼女に良い印象を与えることができました。あれはXNUMX年前のことだった。今でも同じ講師の同じクラスを受講しています。

インプロを行うことで、研究への取り組み方は変わりましたか?

自分の考えごとに過度に批判的にならないようにするのは良い習慣です。これはコラボレーションの場合に特に役立ちます。私は他の人と仕事をするときに、「でも、その考えは次の理由でうまくいきません。それは文字通り真実ではありません。」インプロでは、常にパートナーの言うことを受け入れる必要があります。特に学生と一緒に研究をしているときは、それが良い姿勢だと思います。間違っているとわかっているからといって、彼らの発言を無視しないでください。 100% 正しいわけではない良いアイデアもたくさんあります。

どのような？

問題を直観的に理解しようとする場合、役立つことの 1 つは、単純化する仮定から始めることです。これらの仮定は通常は真実ではありませんが、ロードマップを作成するのに役立ちます。 「もしゾウがいたら山を越えられるのに。」と言ってみましょう。もちろん象は飼っていません。でも、もしそうするなら、私ならこうするだろう。」そして、「そうか、このステップには象は必要ないかもしれない」と気づきました。ラバなら大丈夫だよ。」

ロールプレイング ゲームへの愛についてはどうでしょうか。それがあなたの仕事に影響を及ぼしていますか?

それは私の研究すべてに影響を与えたわけではないかもしれませんが、私の五つの世界に関する論文には確かに影響を与えました。私はいつもファンタジーや SF に興味があり、さまざまな世界を想像してみました。もしすべてが違っていたら、物事はどうなるでしょうか?

ロールプレイング ゲームは、なぜ仮想の世界を探索するのにこれほど魅力的な方法なのでしょうか?

推理小説に興味がある人は、常に世界を発明してきました。トールキンはそのことで最も有名であり、彼の世界が実際に生きているように感じるほどの巨大な想像力を持っていました。想像力がそれほど豊かではない人にとって、それを達成するための最良の方法は、自分の設定やゲームに人々を招待することです。それを行う方法です。今、それは私の世界だけではありません。私が想像していたとおりに始まったかもしれませんが、他のコラボレーションと同じように、他のみんなの貢献のおかげで、それをはるかに超えて進化しました。