NP困難・NP完全とは（全体像）
これらは、「その問題はどれくらい難しいか」を分類する考え方（計算複雑性の理論）。難しさを段階で表す。
まず3つの言葉を押さえる。
- P … 速く解ける問題（手早く答えが出る）。例：ソート、最短経路。
- NP … 答えを見せられれば、正しいか速く確認できる問題。「解くのは大変でも、確認は速い」。
- NP完全 … NPの中でいちばん難しいグループ。互いに密接につながっている。
よくある誤解が「NP＝解けない」。正しくは、NPは「答えの確認が速い」問題のことで、解けないわけではない（ただし、解くのに時間がかかる場合がある）。つまり、NPは「解けない」ではなく「答えを見せられれば正しいか速く確かめられる」問題、というわけだね。
詳しく：クラスの関係と代表例だけ覚えれば戦える
ここが記事の心臓部。まずはクラスの意味。
難しさのクラス
| クラス | 意味 |
|---|---|
| P | 速く解ける（手早く答えが出る） |
| NP | 答えを見せられれば、正しいか速く確認できる |
| NP完全 | NPの中でいちばん難しいグループ |
| NP困難 | NP完全と同等以上に難しい（NPの外も含む） |
押さえるのは2点。1つはNP完全とNP困難の違い。NP困難はNP完全と同等以上に難しい範囲で、NP完全より広い（NPに入らないものも含む）。「NP完全＝NP困難」ではない。
もう1つは、NP完全のグループは深くつながっていること。そのうちのどれか1つでも速く解ける方法が見つかれば、グループ全部が速く解ける——という関係がある。
代表的なNP完全・NP困難の問題
| 問題 | 内容 |
|---|---|
| 巡回セールスマン問題（TSP） | すべての都市を最短で1周する順番を求める |
| ナップサック問題 | 容量制限のなかで価値を最大にする選び方 |
これらの問題は、規模が大きくなると現実的な時間では正確に解けないことがある。そこで実務では、近似アルゴリズム（完璧ではないが、そこそこ良い答えを速く出す方法）で対応する。
なお、「P＝NPか？（速く確認できる問題は、速く解けるのか）」は、まだ答えの出ていない有名な未解決問題だ。
わかりやすく言い換えると
要するに、これは「問題の手ごわさのランク分け」だ。
①P … すぐ解けるやさしい問題（計算がすぐ終わる）
②NP … 解くのは大変でも、答えを見せられれば「正しい」とすぐ確認できる問題（ジグソーパズルは作るのは大変でも、完成品が正しいかは一目で分かる）
③NP完全 … NPの中でいちばん手ごわいグループ。1つ攻略できれば全部攻略できる、という運命共同体
巡回セールスマンのように大きくなると正確には解けない問題は、近似で「だいたい良い答え」を出して実務をこなす、というわけだね。
試験のツボ
🔴 一番出る：NPの意味
①NP＝「解けない」ではなく「答えの確認が速い」問題
②P＝速く解ける、NP完全＝NPでいちばん難しいグループ
🔴 次に出る：NP完全とNP困難の違い
①NP困難はNP完全と同等以上に難しい（NP完全より広い）
②NP完全はどれか1つ速く解ければ、グループ全部が速く解ける
🟡 押さえると安定：代表例と実務対応
①巡回セールスマン問題・ナップサック問題が代表
②大きな問題は近似アルゴリズムで対応する
よくある間違い
①「NPとは『解けない問題』のことである」→ ✗ NPは「答えの確認が速い問題」。解けないわけではない（解くのに時間がかかる場合はある）。
②「NP完全とNP困難はまったく同じものである」→ ✗ NP困難はNP完全と同等以上に難しく、NP完全より広い（NPの外も含む）。
③「巡回セールスマン問題は、規模が大きくても必ず一瞬で正確に解ける」→ ✗ 規模が大きいと正確には解きにくく、近似アルゴリズムで対応する。
試験での出題パターン
実際の問題でたしかめてみよう。
オリジナル問題1（NPの意味）
NPに関する次の記述のうち、正しいものはどれか。
- NPとは、どんな方法を使っても絶対に解くことができない問題のことである
- NPとは、答えを見せられても正しいか確認できない問題のことである
- NPとは、つねに一瞬で速く解けることが保証された問題のことである
- NPとは、答えを見せられれば正しいか速く確認できる問題のことである
解答は 4 だよ。
NPは「答えを見せられれば、正しいか速く確認できる」問題なんだ。「解けない」わけではなくて、確認が速い、というのがポイントだよ。
選択肢1は「絶対に解けない」が誤り。選択肢2は「確認できない」が誤り。選択肢3は「つねに一瞬で解ける」が誤り（それはPに近い）だよ。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✗ | 解けないわけではない |
| 2 | ✗ | 確認が速いのがNP |
| 3 | ✗ | 速く解けるのはP |
| 4 | ✓ | 答えの確認が速い問題 |
オリジナル問題2（NP完全とNP困難）
NP完全とNP困難の関係に関する次の記述のうち、正しいものはどれか。
- NP完全とNP困難はまったく同じもので、区別する必要はないものである
- NP困難はNP完全と同等以上に難しく、NP完全より広い範囲を指している
- NP困難はNP完全より簡単で、すべて速く解けることが分かっているものだ
- NP完全はNP困難より広く、NPの外の問題もすべて含んでいるものである
解答は 2 だよ。
NP困難はNP完全と同等以上に難しく、NP完全より広い範囲（NPの外も含む）を指すんだ。「NP完全＝NP困難」ではない、というところがポイントだよ。
選択肢1は「まったく同じ」が誤り。選択肢3は「NP困難のほうが簡単」が誤り。選択肢4はNP完全とNP困難の広さが逆だよ。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✗ | 別の概念 |
| 2 | ✓ | NP困難はNP完全以上で広い |
| 3 | ✗ | NP困難のほうが難しい |
| 4 | ✗ | 広いのはNP困難 |
オリジナル問題3（代表例と対応）
NP完全・NP困難の代表例と対応に関する次の記述のうち、正しいものはどれか。
- 巡回セールスマン問題は規模が大きくても、必ず一瞬で正確に解けるものだ
- NP困難な問題は実務では一切扱われず、研究の中だけに存在するものである
- 巡回セールスマン問題などは大きいと解きにくく、近似アルゴリズムで対応する
- NP完全・NP困難の問題は、近似アルゴリズムでは決して扱えないものである
解答は 3 だよ。
巡回セールスマン問題などは規模が大きいと正確には解きにくく、近似アルゴリズム（そこそこ良い答えを速く出す方法）で対応するんだ。実務ではこれが現実的だよ。
選択肢1は「一瞬で正確に解ける」が誤り。選択肢2は「実務で扱われない」が誤り。選択肢4は「近似で扱えない」が逆だよ。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✗ | 大きいと正確には解きにくい |
| 2 | ✗ | 実務で近似により扱う |
| 3 | ✓ | 大きい問題は近似で対応 |
| 4 | ✗ | 近似アルゴリズムで対応する |
まとめ
押さえどころ
- 🔴 NPの意味 ＝ 「解けない」ではなく「答えの確認が速い」問題。P＝速く解ける、NP完全＝NPで最難。
- 🔴 NP完全とNP困難 ＝ NP困難はNP完全と同等以上に難しく、NP完全より広い（NPの外も含む）。
- 🟡 代表例と対応 ＝ 巡回セールスマン問題・ナップサック問題が代表。大きい問題は近似アルゴリズムで対応。
次に学ぶ
- 最適化問題（メタヒューリスティック） ── NP困難な問題を近似で解く手法（遺伝的アルゴリズムなど）。実務での対応が具体的になる。
- 計算量詳細（Big-O・Ω・Θ） ── 「速く解ける」「時間がかかる」を表す計算量の考え方。難しさのクラスの土台になる。
執筆: SikakuQuest編集部