応用数学XC（本郷） - 理学部 - 東京大学授業カタログ

応用数学XC（本郷）

オートマトン・チューリング機械・計算複雑性 Automaton, Turing machine, and complexity

P=NP問題に代表される計算複雑性の理論の基本的事項を理解することを目標とする。個々のアルゴリズムの計算量ではなく，計算量のクラスについて調べるのが計算複雑性の理論である。種々のクラスの間の相互関係を研究するのが目的である。個々のアルゴリズムの計算量は別に調べないといけないことだが，計算複雑性の概要に関する実践的感覚をもっていることは重要であるし，今では誰もが知っておくべき常識となっている。
　そのためにはまず「計算」を数学的に形式化するところから始めなければならない。講義の前半ではその形式化としてチューリング機械を導入する。感覚をつかむために初学者でも理解しやすいオートマトンから始める。

MIMA Search

授業計画

　初等的な計算モデルとしてオートマトンやそれに付随する概念について述べる。決定性・非決定性の違い，正規言語との同等性，ポンプ補題を紹介する。割と容易に理解できる単純なモデルだが重要度が低いわけではない。バックトラックを必要とせずに高速に実行できる計算クラスを与える。　計算モデルとしてチューリング機械を導入する。後半の講義で述べる計算複雑性はチューリング機械をベースに定式化される。計算可能・計算不可能性，停止性問題の計算不可能性，帰着について述べる。計算の概念を数学的に定式化する方法にはいろいろあるが，チューリング機械は最も多用されるものである。　計算複雑性の種々のクラスを導入しその性質を調べる。複雑性には時間によるものと空間によるものがある。時間に関する複雑性にはクラスPやNP等がある。空間に関してはPSPACE等がある。P=NP問題の定式化，多項式時間還元，NP完全問題，サビッチの定理，PSPACE完全問題について述べる。時間があれば階層定理，オラクルによる相対化，確率チューリング機械，クラスBPP・IPについて述べる。