チューリングマシンの拡大と複雑性

2021/02/26 マルゼミ

概要と申し込み https://turing-complex.peatix.com/

講演ビデオ「チューリングマシンの拡大と複雑性」

 

  1. Part 1 複雑性理論の基本概念
  2. Part 2 チューリングマシンと複雑性
  3. Part 3 複雑性理論の転換

講演資料「チューリングマシンの拡大と複雑性」
ダウンロード

講演資料 Viewer

参考資料 第一部 複雑さについて考える

  1. 複雑さについて (blog)
  2. 無限について (blog)
  3. 有限の「限界」を考える (blog)
  4. 「多項式時間」について (blog)
  5. 長い長い計算 (blog)
  6. 関数の増大のイメージとBig O記法 (blog)
  7. 「時間計算量」と「空間計算量」(blog)
  8. 「やさしい問題」と「むずかしい問題」(blog)
  9. 「NP-完全」問題 — 僕の反省 (blog)
  10. グラフの3色塗り分け問題 (blog)
  11. グラフの三色塗り分け問題の複雑性 (blog)
  12. N**Pクラスの階層とMIP*=RE定理 (blog)

  13. 有限の中の無限、無限の中の有限 (blog)

参考資料 第二部 チューリングマシンと複雑性 

  1. 全体の概要  (pdf  video)
  2. 非決定性チューリングマシンとNPクラス ( pdf video )
  3. 非決定性チューリングマシンと 決定性チューリングマシン ( pdf video )
  4. NP完全と数学的証明 ( pdf video )
  5. 確率的チューリングマシンと BPPクラス ( pdf video )
  6. Interactive Proofと証明概念の変化 ( pdf video )
  7. 量子チューリングマシン (pdf video)

ショートムービー リスト

  1. 全体の概要