計算複雑性理論入門
はじめに
セミナータイトルを、「コンピュータと数学 2」から「計算複雑性理論入門」に変更しました。
今回のセミナーは、前回のセミナーと基本的な議論は連続しています。
それは、コンピュータとAI技術の次の未来を展望するうえで、人間の二つの基本的能力である「言語能力」と「数学的能力」の「統合」の課題が重要だという議論です。
そうした立場から、前回のセミナー「コンピュータと数学 -- TuringからVoevodskyまで」では、コンピュータにはそもそも「数学的能力」が備わっているのではという問題意識を述べてきました。
そこでは、コンピュータの持つ数学的能力の(再)発見の突破口となった「計算 ＝ 証明 = プログラミング」という認識の成立の場所である「型の理論」を取り上げ、実際にコンピュータによる証明の例を紹介しててきました。
今回のセミナー「計算複雑性理論入門 -- Turingマシンから量子コンピュータまで」では、こうした論点をさらに深める上で、計算科学の代表的な数学理論である「計算複雑性理論」に注目しようと思います。
Gödelの「不完全性定理」と「計算可能性理論」
少し歴史を遡ってみましょう。
現実にコンピュータが登場するはるか以前の1930年代に、Gödelの「不完全性定理」の強い衝撃の中で、「数学的に計算できるものとは何か？」という問いの中から、Gödel - Church - Turing らによって、「計算可能性理論」が生まれました。
「計算可能性理論」は、計算可能なものと計算不可能なものとを区別する基準を数学的に定義することに成功します。それは、ゲーデルの「不完全性定理」の背後にある構造の理解を可能とする「計算不可能性理論」と言ってもいいものです。
そのエッセンスは、「計算可能な計算はすべて、ある帰納的チューリングマシンによって実行される」という「チャーチ=チューリングのテーゼ」です。
彼らが切り開いたのは、数学的能力をはじめとして人間の知性と認識能力自身の限界を数学的分析の対象とするという、これまでの数学にはなかった新しい探究の道でした。彼らが始めた「計算可能性理論」が「計算複雑性理論」の第一世代だと考えていいと思います。
計算複雑性理論の登場
ただ、それで計算可能なものの境界が明確になったかというと、必ずしもそうではありませんでした。「計算可能性理論」では理論的には「計算可能」とされる計算でも、実際には計算できそうもないものがあることは、数学的には知られていました。
1950年代にはコンピュータが登場します。1960年代に入ってその利用は飛躍的に拡大を始めます。そうした背景の中で、1970年代になって、「計算複雑性理論」が登場します。
それは、先に述べた「理論的には計算可能だが、現実には手に負えない」領域も視野に入れて、計算可能なものの世界の内部により実際的でより現実的な分類、簡単に計算可能な問題から計算が難しい問題の階層を新たに導入しようという理論です。こうして導入された分類を、「計算複雑性」といいます。
「計算複雑性理論」の実際の成立の過程は先行した「計算可能性理論」の影響を受けもう少し複雑なのですが、それは、客観的には、「コンピュータで実際に計算可能なものとはどういうものなのか？」を考える理論だと考えていいと思います。
よく混同されるのですが、それはフラクタルやカオス等を対象とした、いわゆる「複雑系の理論」とは異なるものです。
今、考えるべきこと
では、なぜ 「生成AI」が大ブレイクしている今、1930年代や1970年代に起源を持つ「計算可能性理論」や「計算複雑性理論」また、1980年代に起源を持つ「型の理論」といった「古い理論」に注目するのでしょう？
それは、冒頭に述べた「コンピュータとAI技術の次の未来を展望する」という問題意識から発するものです。
私たちは、「機械の知能は、どこまで発展しうるのか？」という問題を考える必要があります。重要なことは、その問題は、「我々人間の認識は、どこまで発展しうるのか？」という問題と同時に提起されているということです。
楽観論者も悲観論者も入り混じっているのですが、我々がそうした問題の前に立たされていることは、多くの人が、感じていることだと思います。
なぜ「計算複雑性理論」なのか？
「計算複雑性理論」は、人間の数学的な認識能力の拡大とその限界を「現実的」に境界付けようという理論なのですが、その理論は、基本的に、「チャーチ＝チューリング・テーゼ」に基づいて計算という人間の数学的能力に「チューリング・マシン」という機械的なモデルを与えることで展開します。
それは、人間が可能な計算の現実的な限界の理論であると同時に、そのモデルである機械が可能な計算の限界の理論でもあるのです。
それは、人間の認識の限界の理論であると同時に、機械の認識の限界の理論でもあるのです。
「計算複雑性理論」が示すそうした視点は、我々が今考えるべき、機械と人間の認識能力の発展の可能性について、また、機械と人間の未来での関係について、多くの示唆を与えると僕は考えています。
「計算複雑性理論」を学ぼう
「計算複雑性理論」は、けっして古い理論ではありません。それは、「人工知能論」の基本的な数学理論として、十分に有効だと思います。
この間の経験に照らせば、先行した数学的理論が、コンピュータの世界で技術的な応用を獲得するまで、数十年の時間を要することは、珍しいことではありません。
今回のセミナーでは、前半で「多項式時間と指数関数的時間」「P問題ととNP問題」「NP完全問題」といった「計算複雑性理論」の基本的な概念を紹介しようと思います。
セミナーの後半では、チューリング・マシンの拡大に伴って、対応する複雑性のクラスが拡大し、「拡大されたチャーチ＝チューリング・テーゼ」のもとで、そうした複雑性クラスの拡大が、人間＝機械の能力の拡大として解釈されうることを見ていきたいと思います。
こうしてコンテキストのもとで、「量子コンピュータ」の位置付けを明確にすることができると思います。
計算可能性理論と計算複雑性理論
計算可能性理論とChurch-Turing Thesis
↑ 見出しクリックでYouTubeへ； ↓ pdfはスクロールで全文読めます
計算複雑性理論とは何か
↑ 見出しクリックでYouTubeへ； ↓ pdfはスクロールで全文読めます
計算複雑性の基本的階層
「時間計算量」と「空間計算量」
↑ 見出しクリックでYouTubeへ； ↓ pdfはスクロールで全文読めます
NP 問題
↑ 見出しクリックでYouTubeへ； ↓ pdfはスクロールで全文読めます
NP-完全問題
↑ 見出しクリックでYouTubeへ； ↓ pdfはスクロールで全文読めます
Interlude
Tao、証明支援システムを語る
↑ 見出しクリックでYouTubeへ； ↓ pdfはスクロールで全文読めます
チューリングマシンの拡大と計算複雑性
非決定性チューリングマシンとNPクラス
↑ 見出しクリックでYouTubeへ； ↓ pdfはスクロールで全文読めます
確率的チューリングマシンとBPPクラス
↑ 見出しクリックでYouTubeへ； ↓ pdfはスクロールで全文読めます
量子チューリングマシンとBQPクラス
↑ 見出しクリックでYouTubeへ； ↓ pdfはスクロールで全文読めます
主要な計算複雑性クラスと対応するチューリングマシン
↑ 見出しクリックでYouTubeへ； ↓ pdfはスクロールで全文読めます
Church-Turing Thesisの変化と量子情報理論
↑ 見出しクリックでYouTubeへ； ↓ pdfはスクロールで全文読めます
