【高校生向け】 寄り道すると急に難しくなる？ ―ルート検索から始まる計算複雑性理論―

自宅からNIIまでの最短、最安、または最も快適な通勤ルートを検索するのは、スマホですぐに解決できる問題です。しかし、途中でついでにコンビニ、書店、カレー屋などに（どんな順でもいい）訪ねる最適のルートを求めれば、話は一変します。途中の立ち寄る場所の順によって所要時間は大きく変わりますが、手作業で全ての順を試すのに時間がかかりそうです。
例のように、世の中に遭遇している問題は「簡単に解けるもの」と「簡単に解けられなさそうなもの」に分けられていそうで、計算複雑性理論はその問題の区別を解明する学問です。
この講義では、計算複雑性理論に計算問題の困難さを比較するための基本概念である「還元」について議論します。古典的な例を挙げてから、最前線の研究においても、還元が重要な役割を果たしていると解説します。

※アーカイブ動画は本ページにて後日公開予定です。