【アルゴリズム・計算理論】現代数学・情報科学の最大未解決問題！「P = NP? 問題」と「NP完全問題」

基本情報・応用情報技術者試験から高度情報処理技術者試験（ITストラテジスト、エンベデッドなど）まで、計算量理論の根本概念として知られる「P = NP? 問題」と「NP完全問題」のまとめカードです。

1. P = NP? 問題 とは

「クラスNPが、クラスPを、真に含むこと（P ≠ NP）の証明」

「答えの正しさを確認するのが簡単な問題（NP）」は、「解くこと自体も簡単な問題（P）」なのか、それとも「解くのが本質的に難しい問題を含んでいるのか（P ≠ NP）」という、いまだ証明されていない未解決問題です。

2. NP完全問題 とは

NPに属する問題の中で「最も難しい問題のグループ」です。以下のどちらかを証明することで、P = NP? 問題全体の決着がつきます。

【NP完全問題と P = NP 決着の条件】

・NP完全問題が、ひとつでも、Pに属さないこと（P ≠ NP）の証明
➔ 「NPには、どうしても多項式時間で解けない難しい問題が存在する」と証明される。

あるいは

・NP完全問題が、ひとつでも、Pに属すること（P = NP）の証明
➔ 「一番難しい問題すら多項式時間で解けるため、NPの全問題が効率よく解ける」と証明される。

3. クラスP と クラスNP の基本概念

クラス	意味・定義	具体的な例
クラス P	現実的な時間（多項式時間）で「解くことができる」問題。	ソートアルゴリズム、最短経路問題（ダイクストラ法など）
クラス NP	提示された答えが正しいかどうかを、現実的な時間で「判定・検証できる」問題。	数独（N×N）、巡回セールスマン問題、素因数分解問題
NP完全	NPの中で最も難しく、すべてのNP問題を効率よくこの問題に変換（還元）できる問題。	3-SAT（3充足可能性問題）、ナップサック問題、ナップサック問題の判定版

---

4. まとめ

「解くのが難しい問題（NP）」のうち、どれか1つでも効率よく解く方法（Pに属すること）が発見されれば、すべてのNP問題が一気に解ける（P = NP）ことになります。現代の暗号技術（RSA暗号など）は「解くのが難しい（P ≠ NPである）」ことを前提に構築されています。