統計力学と計算複雑性理論の二分野は、物理学と計算機科学という異なる出自を持つ一方で「単純な構成要素が多数集まった際に非自明な振る舞いを見せる」という広義の多体現象を捉えるモチベーションを共有する営みだと言える。

このような抽象的な類似性以外にも、量子計算などにおける量子超越性の定式化; 量子モンテカルロ法の負符号問題や基底状態の同定など経験的に難しいとされる課題の困難さの理論的確立; ハミルトニアンや物質の状態相の複雑性による定性的区別; などの物理的にも重要な問題を数学的に解決する枠組みが計算複雑性理論であり、近年の物理学と計算機科学の接近における重要分野となっている。

本講義では「相転移・フラストレーション・量子」という三つの非自明な多体現象にまつわるキーワードを中心に、統計力学の視点から計算複雑性の基礎概念を解説することで、理論物理の初学者が抵抗感なくこれらの概念を取り扱えるようになることを目標にしつつ、物理と関わる未解決問題など最新の話題も提供する。