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