講演資料
講義資料スライドの表紙です。上のスライド画像をクリックすると、同じ画面のまま全編のPDF資料を快適に閲覧・印刷することができます。
セミナーの概要
本セミナー「計算複雑性理論入門 ――Turingマシンから量子コンピュータまで」は、生成AIが社会に浸透し始めた現代において、「機械の知能はどこまで発展しうるのか」という根源的な問いを、計算科学の数学的基盤から再検討しようとする意欲的な試みです [p.1, p.17]。
議論の出発点は1930年代にまで遡ります。ゲーデルの「不完全性定理」が数学の自己完結性という夢を打ち砕いた衝撃の中で、Gödel・Church・Turingらは「数学的に計算できるものとは何か」という問いに挑み、「計算可能性理論」を生み出しました [p.12, p.13]。そのエッセンスは「計算可能な計算はすべて、ある帰納的チューリングマシンによって実行される」というChurch-Turing Thesisに集約されます [p.39]。しかしこの理論は、原理的・抽象的な限界しか与えず、「理論的には計算可能だが現実には手に負えない」問題群の存在を浮き彫りにしました [p.47]。
この実践的課題に応えるため1970年代に登場したのが「計算複雑性理論」です。Cook・Levin・Karpらが切り開いたこの理論は、計算可能な世界の内部に「易しい(P)」と「手に負えない(NP)」という質的・量的階層を導入し、NP完全という普遍的な困難さの概念を確立しました [p.105, p.112]。さらに非決定性・確率的・量子チューリングマシンへとモデルを拡大することで、NP・BPP・BQPという複雑性クラスの階層が構築されます [p.195, p.219]。
本セミナーが最も重視する洞察は、この理論が単なる計算科学の枠を超えているという点です。Church-Turing Thesisは、Deutschによって物理的計算可能性の命題へと拡張され [p.231]、さらにGoogleの量子超越性実験(2019年)によって「拡張されたChurch-Turing Thesis」が物理的に反証されるという劇的な展開を迎えます [p.272]。計算複雑性理論は、人間と機械の両方に共通する認識能力の限界を数学的・物理学的に描き出す理論として、量子情報理論・量子重力理論とも接合しながら現代物理学の中核へと進化しつつあります [p.286, p.288]。
講義のロードマップ
ここでは、セミナーの講演資料がどのようなパートから構成されているかを示します。また、それぞれのパートのポイントを紹介します。
■ Part 1: 計算可能性理論と計算複雑性理論
コンピュータが存在するはるか以前に「計算とは何か」という問いが生まれた歴史的文脈を解説し、Church-Turing Thesisと「計算複雑性理論」の登場意義を思想的・数学的に定位します。計算複雑性理論は単なる工学的効率論ではなく、人間と機械に共通する認識の限界を境界付ける理論であるという本セミナーの根本的な問題意識がここで提示されます [p.18, p.25]。
■ Part 2: 複雑性クラスの基本階層
計算可能な世界の内部に「時間計算量」と「空間計算量」という尺度を導入し、P・NP・PSPACE・EXPなどの複雑性クラスの階層を体系的に構築します。NP完全という概念の発見がいかに革命的であったかを、Cook-Levin定理とKarpの還元の手法を通じて解説します [p.97, p.98, p.111, p.112]。
■ Part 3: チューリングマシンの拡大と計算複雑性
決定性チューリングマシンを非決定性・確率的・量子チューリングマシンへと段階的に拡大することで、NP・BPP・BQPという複雑性クラスの対応関係を明らかにします。Church-Turing Thesisが物理法則との関連でどう変容してきたかを追い、量子情報理論が現代物理学の中心理論へと発展する様子を描きます [p.152, p.267]。
ページのナビゲート