NP困難とは：NP完全・NPハードの定義と代表例（巡回セールスマン問題・停止問題）

NP困難・NP完全・NPハードの定義と代表例（巡回セールスマン問題・停止問題）を図解でわかりやすく解説。難易度や検証可否の違いを具体例で理解するための入門ガイド

NPとは

ここで扱う「NP難問」は主にYES/NO（判定）問題のことを指します。複数ある計算問題のうち、NPとは「与えられた解（証明、certificate）を多項式時間で検証できる」問題のクラスです。つまり、ある入力に対して「はい（YES）」であることを示す短い証拠が与えられれば、その証拠を効率よく（多項式時間で）チェックできます。

NPハードとNP完全（NP-complete）

NPハード（NP-hard）とは、NPに属するすべての問題が多項式時間でその問題に還元（変換）できるような問題を指します。言い換えれば、NPにあるどの問題よりも少なくとも同じかそれ以上に難しい問題です。注意点として、NPハードの問題は必ずしもNPに含まれる（効率に検証できる）とは限らず、そもそも決定可能でない（決定不能）問題や、答えが数値の最適化問題など非判定問題もここに含まれ得ます。

NP完全（NP-complete）は、両方の性質を満たす問題で、「NPに属する」かつ「NPハードである」問題です。つまり、NPの中で最も難しい問題の集合と考えられます。もしあるNP完全問題を多項式時間で解けるアルゴリズムが見つかれば、全てのNP問題を多項式時間で解けることになり、これは有名なP vs NP問題に直結します（この問題は現在でも未解決です）。

代表例：トラベリングセールスマン問題（NP完全の例）

例（NP完全）:

ある旅行中のセールスマンが、自宅を出発点にして100の都市を回りたいと考えています。ガソリンが限られているため、合計で1万キロ以内しか走れません。彼は「すべての都市を合計1万キロ以下で訪問できる巡回路（ハミルトン回路）が存在するか？」を知りたいとします。

この問題は答えが「はい（存在する）」である場合、その巡回路を提示すれば合計距離を計算して1万キロ以下であることを効率よくアルゴリズムで確かめられます。つまりこれは「与えられた解を多項式時間で検証できる」問題です。こうした判定形式に直したトラベリングセールスマン問題（TSPの判定版）は、代表的なNP完全問題の一つとして知られています（詳しくは トラベリングセールスマン問題 を参照）。

実務では、すべての可能な順列を試すような（指数時間の）全探索より速い一般的なアルゴリズムは知られていませんが、見つかった解が正しいかどうかはすぐに確認できます。この性質が「NPの中で難しい」典型例です。

代表例：停止問題（NPハードだがNPではない・注意点）

例（NPハードだがNPには含まれない）:

次のような非常に単純なプログラムを考えます。

while(true){ continue; }

「このプログラムを与えたとき、それが永遠に実行され続け（止まらない）か？」という問いは「停止問題（halting problem）」として知られます。停止問題はチューリングによって決定不能（任意のアルゴリズムで一般に正しい答えを返せない）であると示されているため、多くの意味で「計算不可能」な問題です。

停止問題は一般にNPには含まれません（NPは決定可能な問題のクラスであるのに対して、停止問題は決定不能だからです）。また、停止問題のような決定不能な問題は、「NPより難しい（あるいは少なくとも同等に難しい）」という直感からNPハード的に扱われることがありますが、この分類は「どの種類の還元（多項式時間還元など）を使うか」によって厳密さが変わる点に注意が必要です。要するに、停止問題は一般的な意味でNPよりずっと難く、かつ効率的に検証できるわけではありません。

実用上の意味と補足

• 「判定問題」と「最適化問題（長さ最小化など）」は密接に関連しますが、NP完全の議論では通常、判定問題として扱います。最適化問題（例：最短巡回）の場合、それに対応する判定問題（閾値以下の長さの巡回路が存在するか）を考えることが多いです。
• NP完全問題に対しては、一般には多項式時間の正確解法は見つかっていませんが、近似アルゴリズムやヒューリスティック（現実的に十分良い解を短時間で得る方法）、あるいは入力のサイズや特性を利用した特殊ケースの高速解法が実用的に用いられます。
• 「NPハード」と「NP完全」を区別することは重要です。NP完全はNPに属しつつNPハードである問題、NPハードはそれより広いクラス（決定不能問題や最適化問題を含む）を指します。

この分野は理論計算機科学・アルゴリズム設計の基礎であり、P vs NPの未解決問題や計算可能性（決定可能性）に関する深い問いと結びついています。興味があれば、還元の形式（多項式時間還元、計算可能性理論での還元など）や具体的なNP完全問題の一覧、近似アルゴリズムの技法（貪欲法、局所探索、半定値計画緩和など）をさらに学ぶと理解が深まります。

質問と回答

Q:NP困難問題とは何ですか?

Q: すべてのNP困難問題に対して、動作する解を素早くチェックすることができますか?

Q: NP問題でもあるNP困難問題のカテゴリは何というのですか?

Q: NP困難問題はすべてNP完全なのでしょうか?

Q: NP困難問題は簡単に解けるのですか?

Q: NP困難問題を解くことで得られるメリットはありますか?

Q: NP困難問題を解く研究は進んでいるのでしょうか?

文字で検索