【エヌピーこんなん】
NP困難 とは？
最終更新:
💡 NPのどの問題も、この問題へ変換できる
NPに属するすべての問題を多項式時間で帰着できる問題の性質。帰着の向き、NP完全との違い、実際の個別問題を解くこととの関係を解説します。
📌 このページのポイント
- NPのすべての問題から、多項式時間で帰着できる
- NP困難な問題自身が、NPに属するとは限らない
- NP困難で、かつNPに属する問題がNP完全
- 個々の入力が必ず解けないという意味ではない
ひよこ NP困難は、「すごく時間がかかる」という意味？
ペンギン先生 時間の印象だけで決める言葉ではないよ。NPに属するどの問題も、その問題へ多項式時間で変換できる、という性質なんだ。変換先を効率よく解ければ、変換前も解けるので、少なくとも同程度に難しいと考えるんだね。
ひよこ 変換の矢印は、どちら向き？
ペンギン先生 NPの問題から、NP困難な問題へ向かうよ。逆向きではないんだ。多項式時間は、入力の大きさの一定のべき乗で処理時間を抑えられるという、計算量の基準だよ。
ひよこ NP完全とは何が違う？
ペンギン先生 NP困難で、さらにNPに属する問題がNP完全だよ。NPでは、答えの候補が正しいかを多項式時間で確認できる。NP困難という条件だけでは、この確認ができるとは限らないんだ。
ひよこ NP困難なら、実際の仕事では諦めるしかない？
ペンギン先生 個別の小さな入力や特別な条件なら解けることもあるし、最適解を保証せずによい解を探す方法もあるよ。すべての入力を正確かつ多項式時間で解く方法があるか、という話と分けて考えよう。
もっと詳しく知りたい人へ
NPの問題は、全部NP困難なの？
そうではありません。NP困難は「すべてのNP問題から帰着できる」という追加の性質です。PはNPに含まれますが、NP全体がNP困難に含まれるという集合関係ではありません。PとNPが同じかどうかは未解決です。
まとめ：ざっくりこれだけ覚えればOK！
「NP困難」って出てきたら「NPのどの問題も効率よく変換できる、少なくとも同程度に難しい問題」と思えばだいたいOK！
📖 おまけ：英語の意味
「NP-hard」 ＝ NPのすべての問題と同等以上に難しい
💬 NPはNondeterministic Polynomial timeの略です。ここでの難しさは感覚的な難易度ではなく、問題を別の問題へ変換する「帰着」で比べます。