アヴィ・ウィグダーソンは 40 年以上にわたり、問題を研究してきました。しかし、計算複雑性の理論家として、彼は必ずしもこれらの問題の答えを気にしているわけではありません。彼は、単にそれらが解決可能かどうか、またその判断方法を知りたいだけであることがよくあります。 「状況はばかげている」と彼は言った ヴィグダーソン、ニュージャージー州プリンストンの高等研究所のコンピューター科学者。質問がどれほど難しいように見えても、それに答える効率的な方法は、手の届かないところに隠れている可能性があります。 「私たちが知る限り、私たちが直面し、解決しようとしているすべての問題について、それを解決できるアルゴリズムが存在する可能性を排除することはできません。これが私にとって最も興味深い問題です。」

今日、ウィグダーソンが優勝者に選ばれました。 AMチューリング賞、計算理論への基礎的な貢献により、コンピューター サイエンスにおける最高の栄誉の 1990 つと広く考えられています。ウィグダーソンの研究は、この分野のほぼすべての分野に影響を与えています。彼の同僚、共同研究者、指導を受けている人たちは、彼は異なる分野の間に予期せぬ架け橋を常に見つけていると言っています。そして、XNUMX 年代から始まったランダム性と計算に関する彼の研究は、今日の研究の基礎となっている数学とコンピューター サイエンスの間の深いつながりを明らかにしました。

マドゥ スーダン2002年にロルフ・ネヴァンリンナ賞（現在はそろばん賞と呼ばれる）を受賞したハーバード大学のコンピューター科学者は、この分野におけるウィグダーソン氏の影響を見逃すことはできないと語った。 「コンピューター サイエンスのどの分野でも、アヴィの研究と実際に関わりを持たずに研究するのは非常に難しいです」とスーダン氏は語った。 「そしてどこにでも、非常に深い洞察が見つかります。」たとえば、1980 年代後半、スーダンはウィグダーソンと協力して、特定の数学関数と多項式の間の関係を調査する論文を作成しました。この仕事がスーダンのキャリア全体の始まりとなった。 「これはアヴィにとって典型的なことです」とスーダンさんは言う。 「彼はあるスペースに入り込み、適切な質問をし、そして次に進みます。」

ウィグダーソンは、ホロコーストの生存者である看護師と電気技師の 1970 人の息子の XNUMX 人としてイスラエルのハイファで育ちました。彼の父親はパズルが大好きで、数学の基本的な考え方に強い興味を持っており、それを子供たちと共有していました。 「彼は私がこのウイルスに感染した人物です」とウィグダーソンさんは語った。 XNUMX 年代にハイファのテクニオンで大学に入学したとき、彼は数学を専攻したいと思っていましたが、両親は代わりに彼をコンピュータ サイエンスに誘導しました。 「彼らは、私が仕事を終えたら仕事があるのが得策だと考えたのかもしれない」と彼は語った。

彼は、本質的に数学的な、深くて答えのない疑問が豊富にある分野を発見しました。彼の初期の画期的な取り組みの 1 つは、一見矛盾に焦点を当てたものでした。それは、数学的記述が証明されたことを、その方法を示さずに他の人に納得させることが可能かどうかというものでした。

「証明を見る人は、証明そのものについて何も学びません。」 ラン・ラズ、プリンストン大学のコンピューター科学者。 1985 年に、シャフィ ゴールドワッサー、シルビオ ミカリ、チャールズ ラックオフはこの概念を導入しました。 ゼロ知識対話型証明、いくつかのステートメントでの使用法を示します。ウィグダーソンは後にミカリとオデッド・ゴールドライヒとともにその考えを詳しく説明し、ある言明が証明できればそれが証明されることを示す条件を提示した。 ゼロ知識証明もある.

「これは暗号化における重要な成果です。それは非常に中心的です」とラズ氏は言いました。ゼロ知識証明を使用すると、メッセージに関する情報を漏らすことなく、秘密鍵を使用してメッセージを正しく暗号化または署名したことを証明できます。 「Avi は暗号化において非常に重要な成果をいくつかもたらしており、これはその中で最も重要なものかもしれません。」

しかし、おそらくウィグダーソンの最も基礎的な成果は別の領域にあります。それは、計算の難易度を ランダム。 1970 年代後半までに、コンピューター科学者は、多くの難しい問題に対して、確率的アルゴリズムとも呼ばれるランダム性を利用したアルゴリズムが、決定論的な代替アルゴリズムを大幅に上回る可能性があることに気づきました。で 1977プルーフたとえば、Robert Solovay と Volker Strassen は、当時の最良の決定論的アルゴリズムよりも速く、数値が素数であるかどうかを判断できるランダム化アルゴリズムを導入しました。

問題によっては、確率的アルゴリズムが決定的アルゴリズムを指す場合があります。 1980 年代初頭、ウィグダーソンはカリフォルニア大学バークレー校のリチャード カープと協力して、ランダム性の概念を、計算的に難しいと考えられている問題、つまり、既知の決定論的アルゴリズムでは妥当な時間内に解決できないことを意味する問題に結びつけることに取り組みました。 「それらが難しいことを証明する方法がわかりません」とウィグダーソン氏は言う。しかし、彼とカープは、特定の難しい問題に対するランダム化されたアルゴリズムを発見し、後にランダム化を解除することができ、その問題に対する決定論的アルゴリズムを事実上明らかにしました。同じ頃、他の研究者は、暗号問題における計算上の強度の仮定によって、一般に非ランダム化がどのように可能になるかを示しました。

ランダム性の不合理な有効性により、彼はランダム性そのものの性質について考えるようになりました。彼は、当時の他の研究者と同様に、問題を効率的に解決するためにそれがどの程度必要なのか、そしてどのような条件下ではそれを完全に排除できるのかについて疑問を抱いていました。 「当初、これが私たち自身の愚かさだけなのか、ランダム性を取り除くことはできないのかは明らかではありませんでした」と彼は言う。 「しかし、より大きな問題は、ランダム性を常に効率的に排除できるかどうかということでした。」彼は、ランダム性の必要性が問題の計算の難しさと密接に関係していることに気づきました。

1994紙、彼とコンピューター科学者のノーム・ニサンはそのつながりを明らかにしました。彼らは、ほとんどのコンピューター科学者が疑っているように、何らかの自然な困難な問題が存在する場合、効率的なランダム化アルゴリズムはすべて効率的な決定論的なアルゴリズムに置き換えることができることを証明しました。 「ランダム性はいつでも排除できます」とウィグダーソン氏は言う。

重要なのは、決定論的アルゴリズムが「疑似ランダム」シーケンス、つまりランダムに見えるが実際はそうではないデータ文字列を使用する可能性があることを発見したことです。彼らはまた、どんな難しい問題でも擬似乱数生成器を構築するためにどのように使用できるかを示しました。擬似ランダム ビット (ランダム ビットの代わりに) を確率アルゴリズムに入力すると、同じ問題に対して効率的な決定論的アルゴリズムが得られます。

スーダン氏は、この論文はコンピュータ科学者がランダム性の度合いを認識するのに役立ち、困難な問題の複雑さとその解決方法を明らかにするのに役立つ可能性があると述べた。 「それは単なるランダム性ではなく、ランダム性の認識です」と彼は言いました。 「それが鍵です。」

スーダンは、ランダム性はどこにでも現れるようだが、実際には見つけるのが非常に難しいと指摘する。 「円周率の数字がランダムに見えるとか、素数の数列がランダムに見えると言われることがあります」と彼は言う。 「それらは完全に決まっていますが、私たちにはランダムに見えます。」ランダム性の認識が今日のコンピューター サイエンスの中心にあると彼は言いました。 「そして、それはアヴィが大いに推進してきたことなのです。」

ランダム性は複雑性理論の強力なリソースとなっていますが、とらえどころがありません。ウィグダーソン氏は、コイン投げやサイコロの出目は真にランダムではないと指摘します。物理システムに関する十分な情報があれば、結果は完全に予測可能です。完全なランダム性はとらえどころがなく、検証するのが難しいと彼は言いました。

しかしウィガーソン氏にとって、コンピューティングの例は、スマートフォンやラップトップ、暗号化アルゴリズムだけでなく、生物学的システムや物理的システムなど、あらゆる場所に存在します。ここ数十年、計算理論の発見により、鳥の群れや選挙結果から体内の生化学反応に至るまで、さまざまな予期せぬ問題に対する洞察がもたらされてきました。 「基本的に、自然のプロセスはすべて計算として見ることができる進化なので、それを計算として研究することができます。ほとんどすべてが計算されます。」