【えぬぴーかんぜんもんだい】
NP完全問題 とは？
最終更新:
💡 候補は確認できる。でも一般に速く解けるかは未解決
NPに属し、NPのどの判定問題からも多項式時間で変換できる問題のクラス。答えの候補を効率よく確認できる一方、すべての入力を多項式時間で解く方法があるかは未解決。SATなどが含まれる。
📌 このページのポイント
- NPに属することと、NP困難であることの両方が必要
- 基本的には、答えがYesかNoかを問う判定問題
- 1つでも多項式時間で解ければ、P＝NPになる
- 全探索しかない、どんな入力も解けないという意味ではない
ひよこ NPは、解けないという意味？
ペンギン先生 違うよ。Yesとなる入力について、答えの候補となる証拠を、入力の大きさに対して多項式時間で確認できる判定問題のクラスだよ。多項式時間は、入力サイズnに対しnの固定のべき乗などで計算時間を抑えられる、という数学的な基準なんだ。
ひよこ 完全って、何が完全なの？
ペンギン先生 NPのどの問題も、多項式時間でその問題へ変換できることが重要なんだ。この性質がNP困難で、さらにその問題自体もNPに属すとNP完全。NPに属するだけ、組合せが多いだけでは、NP完全とは言えないよ。
ひよこ 例を知りたい！
ペンギン先生 SAT（充足可能性問題）が代表例だよ。論理式の変数に真・偽を割り当て、式を真にできるかを問う。割り当ての候補があれば式を評価して確認できる。一方、一般のSATを常に多項式時間で解く方法があるかは、分かっていないんだ。
ひよこ 全パターンを試すしかない？
ペンギン先生 全探索しか方法がない、という証明ではないよ。入力の性質を利用する方法や、専用のソルバーが実際の問題を解ける場合もある。小さい入力だけでなく、特定の構造なら大きな入力も扱えることがある。最悪の場合の計算量と、個々の入力の実行時間を区別しよう。
ひよこ 1つ解ければ、全部解ける？
ペンギン先生 ある1つのNP完全問題を、すべての入力について多項式時間で解ければ、変換を使ってNPの問題を多項式時間で解けるのでP＝NPになるよ。特定の1問が解けた、実測で速かった、という意味ではない。PとNPが等しいかは、2026年10月4日に確認したClayの資料でも未解決だね。
まとめ：ざっくりこれだけ覚えればOK！
「NP完全問題」って出てきたら「NPの問題をまとめて解く鍵になる、難しさの代表格の判定問題」と思えばだいたいOK！
📖 おまけ：英語の意味
「NP-complete」 ＝ NP完全
💬 NPはNondeterministic Polynomial timeの略で、非決定性多項式時間という計算量の分類。難しいという日常の言葉だけで決まるものではないよ。