【中止】やっとわかった、P≠NP予想

セミナー趣旨

　本講義では、理論計算機科学分野で最も有名な数学上の未解決問題であるP ≠ NP予想について解説します。P ≠ NP予想とは、スマートフォンやタブレット、電子機器に埋め込まれたチップなども含めた我々の身の回りにあるコンピュータの情報処理能力に、ある種の本質的な限界があることを予想する数学的な命題です。P ≠ NP予想は、クレイ数学研究所が示した21世紀の重要な７つの数学上の予想に選ばれ、100万ドルの懸賞金がかけられるほど重要性が広く認知されていますが、なぜそれほど興味深い予想であるかを理解するためには、計算量理論と呼ばれる研究分野の基礎知識が必要となります。本講義は特に、
　・P ≠ NP予想の名前は聞いたことはあるけれど、面白さや意味が今ひとつピンとこない
　・チューリング機械やNP完全といった関連する専門用語の意味をきちんと理解したい
　・数学が好きで、学術的な知的好奇心を満たす話題に触れたい
基礎の基礎からP ≠ NP予想を説明します。内容の性質上、講義はコンピュータの具体的な応用から離れた理論的な議論に留まりますが、その分、関連する基本的な事項から解説しますので、受講にあたって予備知識、専門知識は必要ありません。

セミナープログラム

1. はじめに
   1. 計算とは何か
   2. 講義の概観
   3. 準備：文字列，集合
2. 講義で扱う情報処理：判定問題
   1. タスクの符号化
   2. 判定問題
3. 最強の計算モデル：チューリング機械
   1. なぜチューリング機械なのか
   2. チューリング機械の計算時間
   3. オーダ表記，その背後にある考え方
   4. チューリング機械を遠目に見る
4. クラスP
   1. クラスPの定義
   2. クラスPの解釈
   3. クラスPに慣れよう
5. クラスNP
   1. クラスNPの定義
   2. クラスNPの解釈
   3. クラスNPに慣れよう
6. P ≠ NP 予想とは何か
   1. 人間と計算機は同じ？
   2. P ≠ NP 予想の解決に向けて
7. P ≠ NP予想を解決するための土台
   1. 多項式時間帰着
   2. NP困難とNP完全
   3. 様々なNP完全問題
8. おわりに

セミナー講師

内澤　啓（うちざわけい）　氏
山形大学大学院　理工学研究科（工学系）　情報科学専攻　准教授（博士（情報科学））

セミナー受講料

お1人様受講の場合　51,700円[税込]／1名
1口でお申込の場合　62,700円[税込]／1口（3名まで受講可能）

受講申込ページで2～3名を同時に申し込んだ場合、自動的に1口申し込みと致します。

受講について

• 本セミナーの受講にあたっての推奨環境は「Zoom」に依存しますので、ご自分の環境が対応しているか、お申込み前にZoomのテストミーティング（http://zoom.us/test）にアクセスできることをご確認下さい。
• インターネット経由でのライブ中継ため、回線状態などにより、画像や音声が乱れる場合があります。講義の中断、さらには、再接続後の再開もありますが、予めご了承ください。
• 受講中の録音・撮影等は固くお断りいたします。