2.3 計算可能性と複雑性

この章では、計算理論の基本的な概念である「計算可能性」と「複雑性」について解説します。

計算可能性とは、問題がアルゴリズム（手順やプロセス）によって解けるかどうか、つまり「計算できる」かどうかを考える概念です。チューリングマシンはこの「計算可能性」の理論的なモデルとして提案されました。しかし、計算可能性だけでは不十分で、問題を解くためにどれだけの「リソース」（時間やメモリなど）が必要かということも重要です。それが「複雑性」の概念です。

複雑性とは、問題を解くための計算資源（時間、メモリなど）の量を考えるものです。同じ問題でも、その解法（アルゴリズム）によって、解くのに必要な時間やメモリが大きく変わることがあります。そのため、効率的なアルゴリズムを開発することは、コンピュータサイエンスにおいて重要なテーマとなっています。

この章では、これらの概念をさらに深く掘り下げ、それらがどのようにしてPとNPの問題に関連するかを見ていきます。