投稿記事

数学とコンピュータを結びつける

投稿日時: 05/11 システム管理者

2021年3月に,2021年のアーベル賞の受賞者が発表されました.ラズロ・ロヴースLászló Lovász(ハンガリー科学アカデミー・レニェイ数学研究所)とアヴィ・ウィグダーソンAvi Wigderson(プリンストン高等研究所)です.
プレスリリースによると,「理論計算機科学および離散数学への基本的な貢献,および,これらの分野を現代数学の中心的な分野として確立するのに果たした主導的な役割」が評価されました.
アーベル賞は,2002年にノルウェー科学アカデミーによって設立された数学で最も権威のある賞の1つです.ノルウェーの天才数学者ニールス・ヘンリック・アーベル(1802–1829)にちなんで名付けられ,この分野の発展に多大な貢献をした科学者に毎年授与されます.

2021年の受賞者について,ステクロフ数学研究所,シカゴ大学(米国)の数学科アレクサンドル・ラズボロフ教授による解説記事を要約紹介します.
「トリニティオプション-科学」第6号(325),2021年3月23日号
https://elementy.ru/nauchno-populyarnaya_biblioteka/435811/Troitskiy_variant_Nauka_6_325_23_marta_2021_goda


離散数学は,有限の離散的オブジェクトの特性を研究します.その重要な部分は,伝統的には組み合わせ論と呼ばれ,「純粋」数学で生じる構造に動機付けられています.たとえば,組み合わせの観点から,トポロジーの基本である複体の概念は,複体の面に対応する有限集合の閉じたファミリーにすぎません.組み合わせの抽象化は顕著な結果をもたらし,「有用な」(つまり,基本的な数学に適用される)組み合わせ論は,数学界で常に重視されてきたのは当然です.

離散数学は,「ハンガリーの数学」と長い間関連しており,その最も活発な支持者および宣伝者は,ポール・エルデシュでした.ラズロ・ロバースは1948年にブダペスト(ハンガリー)で生まれ,この数学的文化の中で育ちました.特に,彼はかなり早い年齢でエルデシュに会いました.そしてこれは彼のその後のキャリアと展望に非常に大きな影響を与えました.ラズロ・ロバースは,ポール・エルデシュの直接の後継者と見なすことができます.

 

         ラズロ・ロバース

理論情報学の形成
理論計算機科学,または,コンピュータサイエンスは,一般に「計算の複雑さの理論」の基礎が築かれた1970年代頃に独立した分野として出現しました.この分野では,大まかに言えば,アルゴリズムの存在の問題,または多くの場合,それらの効率に与えられた制約を伴うアルゴリズムの非存在が研究されます.

その名称にもかかわらず,理論計算機科学は厳密に数理科学であり,そのすべての成果は,数学の他の分野と同様に,厳密な定義,定理,および補題の形で定式化されています.それにもかかわらず,開発の内部論理とともに,理論情報学もまた,実際のアプリケーションによって大部分が導かれ,時には非常に具体的であります.他の「半応用」分野と同様,それに対する「純粋」数学者の態度は,穏やかではあるが長い間警戒していたことは明らかです.

アヴィ・ウィグダーソンは,1956年にハイファ(イスラエル)で生まれました.彼の学生時代は,理論計算機科学,特に独立した分野としての計算の複雑さの理論の形成に費やされました.プリンストンでの大学院での研究中,アヴィは,複雑性理論の創設者の1人である彼の学術顧問Richard JayLiptonの影響を大きく受けました.ロバースの場合と同様に,理論計算機科学が彼の人生の仕事になりました.

 

         アヴィ・ウィグダーソン

両受賞者の主な成果の1つは,数十年にわたる両方の分野の成熟と形成の過程で,彼らの科学的研究と国際的な教育および普及活動が大きな貢献をしたことです.
理論計算機科学は,コンピュータが操作する対象のほとんどが離散的であるという自然な理由から,離散数学の成果,アイデア,概念を積極的に利用しています.その多くは「純粋な」数学では需要がありませんでした.一方,理論計算機科学のニーズは,離散数学の全く新しい分野の創造につながっており,これは科学の歴史の中で最も成功した共生関係の一つであると思います.この分野から他分野への「アイデアの移転」における最大の功労者は,今年のアーベル賞受賞者なのです.
「純粋」数学者や数学者との関係も,より良い方向に変化しました.たとえば,ラズロ・ロバース(ちなみに,ロシア科学アカデミーの外国人会員)は4年間(2007〜 2010年)国際数学連合の会長を務め,プリンストン高等研究所(IAS)でのアヴィ・ウィグダーソンの役職は数学学校に属しています.この道を歩み始めた当初は,どちらも考えられないことでした.これは,抽象数学の多くの分野に密接に関連する問題,アイデア,定式化が両分野に蓄積され,多くの場合,抽象数学自身の発展に影響を与えることによって,多かれ少なかれ自然な形で起こったことです.この点において,ラズロとアヴィは誰もが認めるリーダー的存在です.

離散性から連続性へ
離散数学の特徴として,連続的ではなく有限的な対象への関心が高まっていることを前述しました.ラズロ・ロバースは,正反対の仮定に基づいた非常に重要なプロジェクトの創設者の一人であり,おそらく主人公です.その結果,非常に大きなグラフやその他の組み合わせ対象物は,10進法の分数が無理数の近似値とみなされるのとほぼ同じ意味(ロバースのアナロジー)で,幾何学的または代数的な性質を持つ自然な連続構造の近似値とみなすことができることがわかりました.その結果,美しく一貫した理論が生まれ,当然のことながら組合せ論だけでなく,代数学,解析学,測度論,統計力学,エルゴード理論など,数学や物理学のさまざまな分野と驚くほど関連していることがわかりました.

ラズロ・ロバースは,優れたモノグラフのLarge Networks and Graph Limitsを書き,すぐにこの分野の古典的なテキストになりました.興味のあるすべての読者にお勧めします.

 

 

 

 

 

 

 

 

 

 

 

 

 

 


疑似乱数理論
アヴィ・ウィグダーソンに最も関連するトピックに名称を付けると,疑似ランダム性の理論でしょう.最初の動機から始めると,最も重要なアルゴリズムの多くが本質的に確率的なことです.つまり,作業で乱数検出器を使用します.ただし,絶対的なランダム性はまれであり,実際には,いわゆる疑似乱数発生器がほとんどの場合使用されます.これは,アルゴリズムがそのような置換に「気付かない」ことを期待して,決定論的手順によって生成されたランダムビットとして渡されます.

擬似乱数理論とは,大まかに言えば,この希望に理論的根拠を与えようとするもので,さまざまなアーキテクチャやパラメータを持つ発生器を構築し,それらが必要な特性を持つことを数学的に証明することができ,同時に,これらの対象や概念は,計算複雑さの理論において,まったく独立した別の用途があることや,対応する構造が,たとえば代数幾何学のような,数学のきわめて古典的な分野に関連していることも,すぐに判明しました.アヴィ・ウィグダーソンは,この分野で誰もが認めるリーダーです.特に,最も重要な構成要素(Nisan-Wigderson発生器)と,複雑さの理論における顕著な影響(Impagliazzo-Wigderson定理)の両方があります.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Kneser仮説
ラズロ・ロバースは,クネーザー予想の証明があります.クネーザーグラフは,代数的組み合わせ論で発生する非常に自然な有限グラフで,タスクは,その色数を計算することです.つまり,エッジで接続された頂点が常に異なる色になるように頂点に色を付けることができる最小の色数を計算します.

 

おそらく,最適な着色を作成するのは簡単です.問題は,それを改善できないことを証明することです.この問題は,25年近くの間,組合せ学的な努力を必要としていましたが,1978年にロバースが発表したエレガントな論文で,厳密に離散的な絵全体を多次元の球体に浸し,実数位相幾何学の基礎的な結果の1つであるBorsuk-Ulamの定理を適用することで解決されました.この証明から,今日では位相幾何学的組合せ論と呼ばれる学問全体が発展し,その方法によって,他のアクセスできない問題の数々が解決されました.

解の系

証明の複雑さの理論では,数学の定理や,あるグラフが与えられた数の色に着色できないという主張,あるコードにエラーが含まれていないという主張など,さまざまな自然な主張の効果的な証明が可能かどうかを研究します.最も重要な証明系は,いわゆる解の系であり,それに基づくアルゴリズムが最も広く実用化されているからです.

解の系を研究する方法はかなり昔から知られていましたが,2001年にEli Ben-SassonとA. Wigdersonが研究するまでは,せいぜい私的なものでした.本研究では,このような証明を分析するための驚くほど簡単な一般的手法を,幅と呼ばれるもう一つの複雑さの尺度の関与に基づいて提案しました.この論文は,証拠の複雑性に関する理論のパラダイムとなり,多くの新しいアイデアやコンセプトを生み出しました.