京都大学 数理解析研究所 第42回数学入門公開講座
https://ocw.kyoto-u.ac.jp/course/1037/
「計算量理論入門 —「複雑さ」をとらえる」
第四日 帰着と完全問題
河村 彰星（数理解析研究所 准教授）
0:00:00 昨日のまとめ
0:06:05 帰着
0:13:13 多項式空間完全問題
0:43:22 複雑さの階層と完全問題
0:47:12 まとめ
0:50:20 質問回答
2021年8月5日（木） 第4回（全4回）
数理解析研究所4階大講演室・オンライン
農具や機械が人に素手よりも大きな力を与えるように、計算機（コンピュータ）は人の頭脳（数学力）を拡張し、問題解決能力を著しく高めました。ではそれによって問題の難しさがだんだん気にならなくなるかというと、さにあらず。歴史的にはむしろ、人が数理的に扱える範囲が広がれば広がるほど、計算機の性能向上や計算手順の工夫では乗り越えられない本質的な複雑さというものが、ますます鮮明に見えてきました。本講義では、この「計算しにくさ」の尺度で様々な数学的対象の複雑度を測るという立場から、計算量理論の枢要な考え方とその適用例や未解決予想について解説します。
数学入門公開講座 バックナンバー（講義ノート）
https://www.kurims.kyoto-u.ac.jp/ja/special-01.back.html
この動画は、クリエイティブ・コモンズ・ライセンス“Attribution-NonCommercial-ShareAlike (CC BY-NC-SA)”が付与されています。 私的学習のほか非営利かつ教育的な目的において、適切なクレジット表記をおこなうことで、共有、転載、改変などの二次利用がおこなえます。 コンテンツを改変し新たに教材などを作成・公開する場合は、同じライセンスを継承する必要があります。 詳細は、クリエイティブ・コモンズのウェブサイトをご参照ください。
