計算量理論入門――「複雑さ」をとらえる

令和3年度 数学入門公開講座

8月2日(月)~6日(金)


農具や機械が人に素手よりも大きな力を与えるように、計算機(コンピュータ)は人の頭脳(数学力)を拡張し、問題解決能力を著しく高めました。ではそれによって問題の難しさがだんだん気にならなくなるかというと、さにあらず。歴史的にはむしろ、人が数理的に扱える範囲が広がれば広がるほど、計算機の性能向上や計算手順の工夫では乗り越えられない本質的な複雑さというものが、ますます鮮明に見えてきました。本講義では、この「計算しにくさ」の尺度で様々な数学的対象の複雑度を測るという立場から、計算量理論の枢要な考え方とその適用例や未解決予想について解説します。

講義資料

リンク