本講義では、理論計算機科学分野で最も有名な数学上の未解決問題であるP ≠ NP予想について解説します。P ≠ NP予想とは、スマートフォンやタブレット、電子機器に埋め込まれたチップなども含めた我々の身の回りにあるコンピュータの情報処理能力に、ある種の本質的な限界があることを予想する数学的な命題です。P ≠ NP予想は、クレイ数学研究所が示した21世紀の重要な7つの数学上の予想に選ばれ、100万ドルの懸賞金がかけられるほど重要性が広く認知されていますが、なぜそれほど興味深い予想であるかを理解するためには、計算量理論と呼ばれる研究分野の基礎知識が必要となります。
　本講義は、基礎の基礎から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. 講義のまとめ
   2. P ≠ NP予想とニューラルネットワークの計算能力